嗯……二维树状数组哦亲~~~
还行吧,只是update 函数和sum 函数的略微变化。
注意到sum还是求 从(1,1)点到(x,y)点的总和,所以求某一区域的和的时候需要四次求和。
AC Memory : 4632 KB Time : 516 ms
代码 :
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int c[1005][1005]; int n; int lowbit(int x) { return x&(-x); } void update(int i,int j,int val) { for(int x = i;x<=n;x+=lowbit(x)) { for(int y = j;y<=n;y+=lowbit(y)) { c[x][y]+=val; } } } int sum(int i,int j) { int s= 0; for(int x = i;x>0;x-=lowbit(x)) { for(int y = j;y>0;y-=lowbit(y)) { s+=c[x][y]; } } return s; } int main() { int m,N,T,x1,x2,y1,y2,x,y; char ch; scanf("%d",&m); while(m--) { memset(c,0,sizeof(c)); scanf("%d%d",&N,&T); getchar(); n=N; while(T--) { scanf("%c",&ch); if(ch == 'C') { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x2++; y2++; update(x1,y1,1); update(x1,y2,-1); update(x2,y1,-1); update(x2,y2,1); } else { scanf("%d%d",&x,&y); printf("%d\n",(sum(x,y) &1)); } getchar(); } printf("\n"); } return 0; }