BZOJ1452: [JSOI2009]Count

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=1452

Solution

练习一下二维树状数组,其实只是多了一层循环QWQ.稍微注意一下容斥就过啦.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,q,opt,ans,x,y,z,x1,x2,y1,y2,num;
int c[305][305][105],f[305][305];
void add(int x,int y,int num,int v){
    for (int i=x;i<=n;i+=i&-i)
    for (int j=y;j<=m;j+=j&-j)
        c[i][j][num]+=v;
}
int get(int x,int y,int num){
    int ans=0;
    for (int i=x;i;i-=i&-i)
    for (int j=y;j;j-=j&-j)
        ans+=c[i][j][num];
    return ans;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++){
        scanf("%d",&f[i][j]);
        add(i,j,f[i][j],1);
    }
    scanf("%d",&q);
    while (q--){
        scanf("%d",&opt);
        if (opt==1){
            scanf("%d%d%d",&x,&y,&z);
            add(x,y,f[x][y],-1);
            f[x][y]=z;
            add(x,y,f[x][y],1);
        }else{
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&num);
            ans=get(x2,y2,num)+get(x1-1,y1-1,num)-get(x1-1,y2,num)-get(x2,y1-1,num);
            printf("%d\n",ans);
        }
    }
}