首页 > 代码库 > Bzoj1452 Count

Bzoj1452 Count

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

题目全是图片,不复制了。

 

 

开100个二维树状数组,分别记录区间内各个颜色的出现位置……

简单粗暴。

 

注意查询操作的读入顺序是x1 x2 y1 y2

 1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=310; 9 int t[101][mxn][mxn];10 int c[mxn][mxn];11 int n,m;12 inline int lowbit(int x){return x&-x;}13 void add(int x,int y,int c,int v){14     while(x<=n){15         int tmp=y;16         while(tmp<=m){t[c][x][tmp]+=v;tmp+=lowbit(tmp);}17         x+=lowbit(x);18     }19 }20 int smm(int x,int y,int c){21     int res=0;22     while(x){23         int tmp=y;24         while(tmp){res+=t[c][x][tmp];tmp-=lowbit(tmp);}25         x-=lowbit(x);26     }27     return res;28 }29 int ask(int x1,int y1,int x2,int y2,int c){30     return smm(x2,y2,c)+smm(x1-1,y1-1,c)-smm(x2,y1-1,c)-smm(x1-1,y2,c);31 }32 int main(){33     int i,j;int x;34     scanf("%d%d",&n,&m);35     for(i=1;i<=n;i++)36         for(j=1;j<=m;j++){37             scanf("%d",&x);38             c[i][j]=x;39             add(i,j,x,1);40         }41     int Q;42     scanf("%d",&Q);43     int x1,y1,x2,y2;44     while(Q--){45         scanf("%d",&i);46         if(i==1){47             scanf("%d%d%d",&x1,&y1,&x);48             add(x1,y1,c[x1][y1],-1);49             c[x1][y1]=x;50             add(x1,y1,c[x1][y1],1);51         }52         else{53             scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&x);54             printf("%d\n",ask(x1,y1,x2,y2,x));55         }56     }57     return 0;58 }

 

Bzoj1452 Count