【bzoj1452】[JSOI2009]Count

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4  5 using namespace std; 6 #define MAXN 302 7  8 int n,m; 9 int G[MAXN][MAXN];10 int tree[102][MAXN][MAXN]; // 颜色，行,列11 12 int lowbit(int x) {return x&(-x);}13 14 void update(int c,int x,int y,int add)15 {16     for(int i=x;i<=n;i+=lowbit(i))17         for (int j=y;j<=m;j+=lowbit(j))18             tree[c][i][j]+=add;19 }20 21 int getsum(int c,int x,int y)22 {23     int ans =0;24     for (int i=x;i>0;i-=lowbit(i))25         for (int j=y;j>0;j-=lowbit(j))26             ans += tree[c][i][j];27     return ans;28 }29 30 int main()31 {32     scanf("%d%d",&n,&m);33     for (int i=1;i<=n;i++)34         for (int j=1;j<=m;j++)35         scanf("%d",&G[i][j]);36 37     for (int i=1;i<=n;i++)38         for (int j=1;j<=m;j++)39         update(G[i][j],i,j,1);40 41     int q;42     scanf("%d",&q);43     while (q--)44     {45         int op;46         scanf("%d",&op);47         if (op==1)48         {49             int x,y,c;50             scanf("%d%d%d",&x,&y,&c);51             update(c,x,y,1);//c颜色x,y +152             update(G[x][y],x,y,-1);//原来颜色xy -153             G[x][y]=c;54         }55         if (op==2)56         {57             int x1,x2,y1,y2,c;58             scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);59             int ans = getsum(c,x2,y2)+getsum(c,x1-1,y1-1);   //c 颜色 i行y1-y2;60             ans -= getsum(c,x1-1,y2);61             ans -= getsum(c,x2,y1-1);62             printf("%d\n",ans);63         }64     }65     return 0;66 }