View Code
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #define N 1005 5 int c[N][N],n; 6 7 int lowbit(int i){ 8 return i&(-i); 9 } 10 11 void update(int x,int y,int val){ 12 int i,j; 13 for(i=x;i<=n;i+=lowbit(i)) 14 for(j=y;j<=n;j+=lowbit(j)) 15 c[i][j]+=val; 16 return ; 17 } 18 19 int getsum(int x,int y){ 20 int s,i,j; 21 s=0; 22 for(i=x;i>=1;i-=lowbit(i)) 23 for(j=y;j>=1;j-=lowbit(j)) 24 s+=c[i][j]; 25 return s; 26 } 27 28 int main(){ 29 int tt,m,x1,x2,y1,y2; 30 char ch[4]; 31 scanf("%d",&tt); 32 while(tt--){ 33 memset(c,0,sizeof(c)); 34 scanf("%d%d",&n,&m); 35 getchar(); 36 while(m--){ 37 scanf("%s",ch); 38 if(ch[0]=='C'){ 39 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 40 x2++; 41 y2++; 42 update(x2,y2,1); 43 update(x1,y1,1); 44 update(x1,y2,-1); 45 update(x2,y1,-1); 46 }else 47 if(ch[0]=='Q'){ 48 scanf("%d%d",&x1,&y1); 49 printf("%d\n",getsum(x1,y1)&1); 50 } 51 } 52 printf("\n"); 53 } 54 return 0; 55 }
更新是从（x，y）到（n，n）；、、因为改变一次（x, y）的值，只会对和它有关的c[x ][y ]有关。
求和是从（x，y）到（1,1）；和（x,y）有关的c[x ][y ]的只在它的下面。