NC5158 D-牛妹吃豆子

Qustion

给你一个的矩阵，有 次操作，每次操作给出四个数字 : 表示牛可乐会将所有满足 这两个条件的位置上放一个豆子。 次询问， 每次询问给出四个数字 : 表示询问所有满足 这两个条件的位置上中总共有多少个豆子.

Solution

二维差分+二位前缀和 ←不会的戳这里←

1. 先根据次操作进行次二维差分。
2. 根据二维差分求出次操作之后的矩阵。
3. 二维前缀和预处理。
4. 查询。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;
const int N = 2e3 + 5;

ll n,m,k,T,D[N][N],pre[N][N];

void solve(int a,int b,int c,int d){
    D[a][b]++,D[c+1][d+1]++,D[a][d+1]--,D[c+1][b]--;
}

void check(int a,int b,int c,int d){
    cout<<pre[c][d]+pre[a-1][b-1]-pre[a-1][d]-pre[c][b-1]<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k>>T;
    for(int i=1;i<=k;i++){
        int a,b,c,D;
        cin>>a>>b>>c>>D;
        solve(a,b,c,D);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            D[i][j]=D[i-1][j]+D[i][j-1]-D[i-1][j-1]+D[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+D[i][j];
        }
    }
    while(T--){
        int a,b,c,D;
        cin>>a>>b>>c>>D;
        check(a,b,c,D);
    }
    return 0;
}