首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。