二维差分

GETexas · 2025-04-02 20:06:53 · 个人记录

当坐标是点的时候 p8648

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+5;

int n, ans;
short a[N][N];

int main() {
    scanf("%d", &n);
    rep(i, 1, n) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        ++a[x1][y1];
        --a[x1][y2];
        --a[x2][y1];
        ++a[x2][y2];
    }
    rep(i, 0, 10000) {
        rep(j, 0, 10000) {
            a[i][j] = int(i > 0 ? a[i-1][j] : 0) + (j > 0 ? a[i][j-1] : 0) - (i > 0 && j > 0 ? a[i-1][j-1] : 0) + a[i][j];
            if(a[i][j]) ++ans;
        }
    }
    printf("%d\n", ans);
    return 0;
}

当坐标是边的时候

#include<iostream>

using namespace std;

int n , m , q;

const int N = 1008;

int a[N][N] , b[N][N];

void insert(int x1, int y1 , int x2 , int y2 , int c){
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main(){
    scanf("%d %d %d" , &n  , &m , &q);

    for(int i = 1 ; i <= n ; i ++ ){
        for(int j = 1 ; j <= m ; j ++){
            scanf("%d" , &a[i][j]);
            insert(i , j , i , j , a[i][j]);
        }
    }

    int x1 , y1 , x2 ,y2 , c;
    while(q --){
        scanf("%d %d %d %d %d",&x1,&y1,&x2,&y2 , &c);

        insert(x1 ,y1 , x2 , y2 , c);
    }

    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= m ; j ++){
            b[i][j] += b[i-1][j] + b[i][j - 1] - b[i - 1][j - 1];
            cout << b[i][j] << " ";
        }
        cout << endl;
    }

    return 0 ;
}