|
|
題目鏈接： 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) 將當(dāng)前范圍內(nèi)
的值和1異或。
2. Q x y (1 <= x, y <= n) 詢問 A[x, y]。
解法：
樹狀數(shù)組
思路：
這題和樹狀數(shù)組的操作正好相反，樹狀數(shù)組是對點更新，成段求和，這題要
求成段更新，對點求值。但是還是可以轉(zhuǎn)化，我們不妨先來考慮一維的情況，給
定一排數(shù)字，每次在區(qū)間進行進行成端加上一個數(shù)，然后詢問某個點的值，很容
易想到線段樹，但是線段樹的常系數(shù)太大，我們試圖用樹狀數(shù)組來解決，方法是
給定區(qū)間[a, b]，如果要求在[a,b]區(qū)間都加上T我們只要在a的位置插入一個T，
然后在b+1的位置插入一個-T，這樣下次詢問某個值k的時候，只要將[1,k]的和求
出來就是k這個位置的值，為什么呢？分三種情況討論：
1. k < a 先前的插入操作不影響此次結(jié)果
2. a <= k <= b a的位置插入T后，統(tǒng)計時值被加了一次
3. k > b。 a的位置有T，b+1的位置有-T，正好抵消
所以結(jié)論成立。
然后就可以擴展到二維的情況，也是一樣，如果對于(x1, y1) (x2, y2)這個
矩形，只要在(x1, y1) (x2+1, y2+1)這兩個點插入T，而(x2+1, y1) (x1, y2+1)
這兩個點插入-T即可。
本題的操作是異或，其實還是一樣的，就是在二進制內(nèi)的無進位加法。
 */
#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;
}
|