对每种颜色开一个二维树状数组

1 #include
      
        2 #include
       
         3 using namespace std; 4 const int maxn=310; 5 int t[110][maxn][maxn],c[maxn][maxn],Q,n,m,k,x,y,xx,yy,col;  6 inline void read(int &k){ 7     k=0; int f=1; char c=getchar(); 8     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 9     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();10     k*=f;11 }12 inline void add(int col,int x,int y,int del){13     for(int i=y;i<=n;i+=i&-i)14         for(int j=x;j<=m;j+=j&-j) t[col][i][j]+=del;15 }16 inline int query(int col,int x,int y){17     int ret=0;18     for(int i=y;i;i-=i&-i)19         for(int j=x;j;j-=j&-j) ret+=t[col][i][j];20     return ret;21 }22 int main(){23     read(n); read(m); 24     for(int i=1;i<=n;i++)25         for(int j=1;j<=m;j++) read(x),c[i][j]=x,add(x,i,j,1);26     read(Q);27     while(Q--){28         read(k);29         if(k==1){30             read(x); read(y); read(col);31             add(c[x][y],x,y,-1); add(col,x,y,1); c[x][y]=col;32         }33         else{34             read(x); read(xx); read(y); read(yy); read(col);35             printf("%d\n",query(col,xx,yy)-query(col,x-1,yy)-query(col,xx,y-1)+query(col,x-1,y-1));36         }37     }38     return 0;39 }