武森《浅谈信息学竞赛中的“0”和“1”》
用树状数组
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int const MAXN = 1010; int c[MAXN * 2][MAXN * 2]; int x,n,t; int LowBit(int x){ return x & (-x); } void Add(int x,int y,int d){ for(int i = x; i <= MAXN; i += LowBit(i)){ for(int j = y;j <= MAXN;j += LowBit(j)){ c[i][j] += d; } } } int Sum(int x,int y){ int ret = 0; for(int i = x;i > 0;i -=LowBit(i)){ for(int j = y;j > 0;j -= LowBit(j)){ ret += c[i][j]; } } return ret; } int main(){ while(~scanf("%d",&x)){ for(int k = 1;k <= x;k++){ scanf("%d%d",&n,&t); memset(c,0,sizeof(c)); for(int i = 0;i < t;i++){ char str[4]; scanf("%s",str); if(str[0] == 'C'){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); Add(x1,y1,1); Add(x2 + 1,y1,1); Add(x1,y2 + 1,1); Add(x2 + 1,y2 + 1,1); } else{ int x,y; scanf("%d%d",&x,&y); printf("%d\n",Sum(x,y) % 2); } } printf("\n"); } } return 0; }