Matrix.(POJ-2155)(树状数组)
一道二维树状数组的题目,比较经典,适合新手练习。
可以打印出来每次操作后矩阵的情况,就能很直观的理解这个树状数组是怎么实现的,他将多余的部分巧妙的重复了偶数次,使得多余部分奇偶不会发生变化。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<map> using namespace std; int T,n,m,bit[1005][1005]; char s[10]; int sum(int a,int b) { int s = 0; for(int i=a;i>0;i-=i&-i) for(int j=b;j>0;j-=j&-j) s+=bit[i][j]; return s; } void add(int a,int b) { for(int i=a;i<=n;i+=i&-i) for(int j=b;j<=n;j+=j&-j){ bit[i][j]++; } } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); memset(bit,0,sizeof(bit)); while(m--) { scanf("%s",s); if(s[0]=='C'){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); add(x2+1,y2+1); add(x1,y1); add(x1,y2+1); add(x2+1,y1); } else { int x,y; scanf("%d%d",&x,&y); printf("%d\n",sum(x,y)%2); } } if(T) printf("\n"); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。