Matrix POJ - 2155
有一个N*N的矩阵,元素值只可能是0或1。现在有两种操作:
1.C x1 y1 x2 y2:将矩形(x1,y1,x2,y2)的元素全部取反。
2.Q x y:查询(x,y)处的值。
输入数据:
第一行给出测试数据的组数X,接下来有X组数据,每组数据的第一行有两个整数N和T。N表示矩阵的边长,T表示操作的次数。N<=1000,T<=50000.接下来T行操作,如上所示。
输出数据:
对于每组数据的每次查询,输出一个整数,表示查询的结果。
这道题可以用二维树状数组的区间修改加单点查询来做,如果矩形(x1,y1,x2,y2)加一,则a[x1][x2]+1;a[x1][y2+1]-1;a[x2][y1+1]-1,a[x2][y2]+1;那么所求点(i,j)的值就是前缀和。
#include <iostream> #include<string.h> using namespace std; const int N = int(3e5) + 99; int sum[1050][1050],n,m; int lowbit(int i) { return i&(-i); } void add(int x,int y,int val) { for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) { sum[i][j]+=val; } } int getsum(int x,int y) { int ans=0; for(int i=x;i>0;i-=lowbit(i)) for(int j=y;j>0;j-=lowbit(j)) { ans+=sum[i][j]; } return ans; } int main() { int t; cin>>t; while(t--) { memset(sum,0,sizeof(sum)); cin>>n>>m; while(m--) { char ch[3]; scanf("%s",ch); if(ch[0]=='C') { int l,b,r,t; cin>>l>>b>>r>>t; add(l,b,1);add(r+1,t+1,1);add(l,t+1,-1);add(r+1,b,-1); } else { int x,y; cin>>x>>y; cout<<getsum(x,y)%2<<endl; } } if(t) printf(" "); } return 0; }