树状数组，inc(x,y)表示对[x-n][y-n]的区域执行一次反转操作，这样，getsum(x,y)将总会包含对[x][y]的操作，即为[x][y]的反转总次数，根据奇偶性判断当前状态。
# include <stdio.h>
# include <string.h>
# define N 1005
int n, c[N][N];
void clr(int nn)
{
int i;
for (i = 1; i <= nn; ++i)
memset(c[i]+1, 0, sizeof(c[0][0])*nn);
}
/******************************************************************/
void inc(int x, int y)
{
int t;
while (x <= n)
{
t = y;
while (t <= n) ++ c[x][t], t += t&(-t);// printf("%d\n", t);
x += x&(-x);
}
}
int getsum(int x, int y)
{
int t, ret = 0;
while (x > 0)
{
t = y;
while (t > 0) ret += c[x][t], t -= t&(-t);// printf("%d\n", t);
x -= x&(-x);
}
return ret;
}
/******************************************************************/
int main()
{
char ins[3];
int X, T, x0, y0, x1, y1;
scanf("%d", &X);
while (X--)
{
scanf("%d%d", &n, &T), clr(n);
while (T--)
{
scanf("%s%d%d", ins, &x0, &y0);
switch(ins[0])
{
case 'C':
{
scanf("%d%d", &x1, &y1);
inc(x0, y0);
inc(x0, y1+1);
inc(x1+1, y0);
inc(x1+1, y1+1);
break;
}
case 'Q': puts((getsum(x0, y0)&0x1) ? "1":"0"); break;
}
}
if (X) putchar('\n');
}
return 0;
}
posted on 2012-09-02 17:29
yajunw 阅读(148)
评论(0) 编辑 收藏 引用