2018牛客网暑期ACM多校训练营（第二场）J Farm（树状数组）

#include <bits/stdc++.h>

using namespace std;
int c[5100010];
int n,m;
int id(int i,int j){
    return i*(m+2)+j;
}

struct nod{
    int x,y,val;
    bool operator < (const nod &b)const{
        if(x==b.x&&y==b.y){
            return abs(val)>abs(b.val);
        }
        if(x==b.x)
            return y<b.y;
        return x<b.x;
    }
};
vector<nod>vd[1100010];
int bit[1100010];
void add(int pos,int x){
    while(pos<=m+1){
        bit[pos]+=x;
        pos+=pos&-pos;
    }
}
int sum(int pos){
    int Sum=0;
    while(pos){
        Sum+=bit[pos];
        pos-=pos&-pos;
    }
    return Sum;
}
int main(){
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif // LOCAL
    int t,x;
    scanf("%d%d%d",&n,&m,&t);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            scanf("%d",&x);
            vd[x].push_back(nod{i,j,0});
        }
    int x1,x2,y1,y2;
    while(t--){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int k;
        scanf("%d",&k);
        vd[k].push_back(nod{x1,y1,1});
        vd[k].push_back(nod{x2+1,y2+1,1});
        vd[k].push_back(nod{x1,y2+1,-1});
        vd[k].push_back(nod{x2+1,y1,-1});
        c[id(x1,y1)]++;
        c[id(x2+1,y2+1)]++;
        c[id(x1,y2+1)]--;
        c[id(x2+1,y1)]--;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[id(i,j)]+=c[id(i-1,j)]+c[id(i,j-1)]-c[id(i-1,j-1)];//被撒肥料总次数
        }
    }
    int ans=0;
    for(int i=1;i<=n*m;i++){
        sort(vd[i].begin(),vd[i].end());
        for(int j=0;j<vd[i].size();j++){
            if(vd[i][j].val==0){
                if(c[id(vd[i][j].x,vd[i][j].y)]==sum(vd[i][j].y))
                    ans++;
            }
            else {
                add(vd[i][j].y,vd[i][j].val);
            }
        }
        for(int j=0;j<vd[i].size();j++)
            if(vd[i][j].val)
                add(vd[i][j].y,-vd[i][j].val);
    }
    printf("%d\n",n*m-ans);
    return 0;
}