bzoj 1452: [JSOI2009]Count ——二维树状数组

escription

Input

Output

Sample Input

Sample Output

1
2

HINT

——————————————————————————————————————————

这道题是裸的二维树状数组.....直接每个颜色弄一个二维的树状数组然后容斥（也不知道算不算）就可以辣

#include<cstdio>

#include<cstring>

#include<algorithm>

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,q,k,f[][];

int s[][][];

#define lowbit(x) x&-x

void ins(int b[][],int x,int y,int v){

    for(int i=x;i<=n;i+=lowbit(i))

    for(int j=y;j<=m;j+=lowbit(j)) b[i][j]+=v;

}

int query(int b[][],int x,int y){

    int sum=;

    for(int i=x;i;i-=lowbit(i))

    for(int j=y;j;j-=lowbit(j)) sum+=b[i][j];

    return sum;

}

int main(){

    int x1,y1,x2,y2,c;

    n=read(); m=read();

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    k=read(),ins(s[k],i,j,),f[i][j]=k;

    q=read();

    for(int i=;i<=q;i++){

        k=read();

        if(k==){

            x1=read(); y1=read(); c=read();

            ins(s[f[x1][y1]],x1,y1,-);

            f[x1][y1]=c;

            ins(s[f[x1][y1]],x1,y1,);

        }

        else{

            x1=read(); x2=read();

            y1=read(); y2=read();

            c=read();

            printf("%d\n",query(s[c],x2,y2)-query(s[c],x2,y1-)-query(s[c],x1-,y2)+query(s[c],x1-,y1-));

        }

    }

    return ;

}