- 1452: [JSOI2009]Count
- Time Limit: 10 Sec Memory Limit: 64 MB
- Submit: 2821 Solved: 1655
- [Submit https://www.lydsy.com/JudgeOnline/submitpage.php?id=1452 ][Status https://www.lydsy.com/JudgeOnline/problemstatus.php?id=1452 ][Discuss https://www.lydsy.com/JudgeOnline/bbs.php?id=1452 ]
- Description
一个 N*M 的方格, 初始时每个格子有一个整数权值, 接下来每次有 2 个操作:
改变一个格子的权值
求一个子矩阵中某个特定权值出现的个数
Input
每一行有两个数字 N,M
接下来 N 行, 每行 M 个数字. 第 i+1 行第 j 个数字表示格子 (i,j) 的初值
接下来输入一个 Q, 后面 Q 行每行描述一个操作
操作 1:
1 x y c, 表示将格子 (x,y) 的值变为 c
操作 2:
2 x1 x2 y1 y2 c, 表示询问所有满足格子中数字为 c 的格子数字
- (n,m<=300,Q<=5000)
- (1<=x<=N,1<=y<=M,1<=c<=100)
- (x1<=x<=x2,y1<=y<=y2)
- Output
对于每个操作 2, 按输入中出现的顺序, 依次输出一行一个整数表示所求得的个数
- Sample Input
- 3 3
- 1 2 3
- 3 2 1
- 2 1 3
- 3
- 2 1 2 1 2 1
- 1 2 3 2
- 2 2 3 2 3 2
- Sample Output
- 1
- 2
- HINT
二维树状数组
就是比一维的多一层循环而已
要注意一定不能写 "for(;x;x-=lowbit(x))"!! 否则会出现令人费解的错误 因为我在从 pascal 转 c++ 的时候没学好 因为我菜
询问的时候用容斥原理乱搞一下即可
- #include<cstdio>
- #include<cmath>
- #include<algorithm>
- #include<cstring>
- #include<iostream>
- #define lowbit(x) x&(-x)
- #define C 100+3
- #define N 300+3
- using namespace std;
- inline int read()
- {
- int x=0,f=1;char s=getchar();
- while(s>'9' || s<'0'){if(s=='-')f=-1;s=getchar();}
- while(s<='9' && s>='0'){x=x*10+s-'0';s=getchar();}
- return x*f;
- }
- int n,m,q;
- int color[N][N],a[C][N][N];
- void add(int x,int y,int c,int f)
- {
- for(int i=x;i<=n;i+=lowbit(i))
- for(int j=y;j<=m;j+=lowbit(j))
- a[c][i][j]+=f;
- }
- int ask(int x,int y,int c)
- {
- int ans=0;
- for(int i=x;i;i-=lowbit(i))
- for(int j=y;j;j-=lowbit(j))
- ans+=a[c][i][j];
- return ans;
- }
- int debug()
- {
- printf("------------\n");
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)printf("%d",color[i][j]);
- printf("\n");
- }
- for(int c=1;c<=3;c++)
- {
- printf("color %d\n",c);
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=m;j++)printf("%d",a[c][i][j]);
- printf("\n");
- }
- }
- printf("------------\n");
- }
- int main()
- {
- n=read(),m=read();
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- int c=read();
- color[i][j]=c;
- add(i,j,c,1);
- }
- //debug();
- q=read();
- for(int i=1;i<=q;i++)
- {
- int opt=read();
- if(opt==1)
- {
- int x=read(),y=read(),c=read();
- add(x,y,color[x][y],-1);
- color[x][y]=c;
- add(x,y,color[x][y],1);
- }
- else
- {
- int x1=read(),x2=read(),y1=read(),y2=read(),c=read(),ans=0;
- ans=ask(x2,y2,c)-ask(x1-1,y2,c)-ask(x2,y1-1,c)+ask(x1-1,y1-1,c);
- printf("%d\n",ans);
- }
- }
- return 0;
- }
- BZOJ 1452
来源: http://www.bubuko.com/infodetail-2551240.html