Count(二维树状数组)

【bzoj1452】[JSOI2009]Count

Description

Input

Output

Sample Input

Sample Output

1
2

 

HINT

题解:对于每一个颜色建一个二维的树状数组O(c*logn*logm)，试了试对每个颜色，每行建一个一维数组，超时了。。。O(c*n*logm)

若一维树状数组不会:http://www.cnblogs.com/haoabcd2010/p/6657393.html

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 #define MAXN 302

 int n,m;

 int G[MAXN][MAXN];

 int tree[][MAXN][MAXN]; // 颜色，行,列

 int lowbit(int x) {return x&(-x);}

 void update(int c,int x,int y,int add)

 {

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

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

             tree[c][i][j]+=add;

 }

 int getsum(int c,int x,int y)

 {

     int ans =;

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

         for (int j=y;j>;j-=lowbit(j))

             ans += tree[c][i][j];

     return ans;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

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

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

         scanf("%d",&G[i][j]);

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

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

         update(G[i][j],i,j,);

     int q;

     scanf("%d",&q);

     while (q--)

     {

         int op;

         scanf("%d",&op);

         if (op==)

         {

             int x,y,c;

             scanf("%d%d%d",&x,&y,&c);

             update(c,x,y,);//c颜色x,y +1

             update(G[x][y],x,y,-);//原来颜色xy -1

             G[x][y]=c;

         }

         if (op==)

         {

             int x1,x2,y1,y2,c;

             scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);

             int ans = getsum(c,x2,y2)+getsum(c,x1-,y1-);   //c 颜色 i行y1-y2;

             ans -= getsum(c,x1-,y2);

             ans -= getsum(c,x2,y1-);

             printf("%d\n",ans);

         }

     }

     return ;

 }