|
|
题目链接： http://poj.org/problem?id=2155
  /**//*
 题意：
对于一个n*n(n <= 1000)的矩阵A，要求作如下操作：
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) 将当前范围内
的值和1异或。
2. Q x y (1 <= x, y <= n) 询问 A[x, y]。
解法：
树状数组
思路：
这题和树状数组的操作正好相反，树状数组是对点更新，成段求和，这题要
求成段更新，对点求值。但是还是可以转化，我们不妨先来考虑一维的情况，给
定一排数字，每次在区间进行进行成端加上一个数，然后询问某个点的值，很容
易想到线段树，但是线段树的常系数太大，我们试图用树状数组来解决，方法是
给定区间[a, b]，如果要求在[a,b]区间都加上T我们只要在a的位置插入一个T，
然后在b+1的位置插入一个-T，这样下次询问某个值k的时候，只要将[1,k]的和求
出来就是k这个位置的值，为什么呢？分三种情况讨论：
1. k < a 先前的插入操作不影响此次结果
2. a <= k <= b a的位置插入T后，统计时值被加了一次
3. k > b。 a的位置有T，b+1的位置有-T，正好抵消
所以结论成立。
然后就可以扩展到二维的情况，也是一样，如果对于(x1, y1) (x2, y2)这个
矩形，只要在(x1, y1) (x2+1, y2+1)这两个点插入T，而(x2+1, y1) (x1, y2+1)
这两个点插入-T即可。
本题的操作是异或，其实还是一样的，就是在二进制内的无进位加法。
 */
#include <iostream>
using namespace std;
#define maxn 1001
int c[maxn][maxn];
int n;
int lowbit(int x)  {
return x & (-x);
}
void add(int x, int y) {
  while(x <= n) {
int ty = y;
while(ty <= n) {
c[x][ty] ^= 1;
ty += lowbit(ty);
 }
x += lowbit(x);
}
}
int sum(int x, int y) {
int s = 0;
if(x > n) x = n;
if(y > n) y = n;
while(x >= 1) {
int ty = y;
while(ty >= 1) {
s ^= c[x][ty];
ty -= lowbit(ty);
}
x -= lowbit(x);
}
return s;
}
int main() {
int t, m;
int i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
memset(c, 0, sizeof(c));
while(m--) {
char str[5];
int x1, y1, x2, y2;
scanf("%s", str);
if(str[0] == 'C') {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
add(x1, y1);
add(x2+1, y2+1);
add(x1, y2+1);
add(x2+1, y1);
}else {
scanf("%d %d", &x1, &y1);
printf( "%d\n", sum(x1, y1) );
}
}
if(t)
puts("");
}
return 0;
}
|