POJ2155 - Matrix （二維樹狀數組）

題目連結：

http://poj.org/problem?id=2155

題目大意：

給定一個矩陣，初始化為0，現在可以進行兩種操作，一種是查詢某個點的值是 0 還是 1。另一種是讓這個矩陣的一個子矩陣内的值取反。

解題過程：

省賽選拔賽的題，太難了直接沒看………

後來補起來，有模闆還是挺容易的。

題目分析：

• 首先這題雖然看起來像是一個區間修改，單點查詢的題，但是可以轉化成單點修改，查詢區間和。
  • 首先考慮一維的情況，我要一段區間取反，假設是 [l, r]。那麼我隻需要

    book[l]+1

    ，

    book[r+1]+1

    ，假設查詢 k 的時候，隻需要查詢前 k 的和 mod 2 的結果即可。
  • 然後這種方法可以推廣到二維，不過這裡要用一下容斥原理。假設修改的子矩陣左上角和右下角分别為 x1 y1 x2 y2，首先

    book[x1][y1]+1

    ,

    book[x2][y2]+1

    ，不過這時要

    book[x1][y2+1]+1

    ,

    book[x2+1][y1]+1

    。

  • 

  • 這裡紅色的就是上面需要标記的點，标記後表示以這個點為左下角的子矩陣内的點全部取反一次。這裡綠色代表取反一次，紫色是取反了兩次，黃色是取反了四次。最後實際進行取反操作的就是要求取反的子矩陣内的點。
• 注意這裡的字首和用二位樹狀數組維護，進行單點更新，單點查詢。

AC代碼：

#include<cstdio>
#include<cstring>
using namespace std;

const int MAX = ;
int data[MAX][MAX], n;

int lowbit(int x) {
    return x&-x;
}

void Add(int x, int y, int w) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= n; j += lowbit(j)) {
            data[i][j] += w;
        }
    }
}

int Sum(int x, int y) {
    int ans = ;
    for (int i = x; i > ; i -= lowbit(i)) {
        for (int j = y; j > ; j -= lowbit(j)) {
            ans += data[i][j];
        }
    }
    return ans;
}

int main() {
    char str[];
    int T;
    scanf("%d", &T);
    while (T--) {
        int k;
        scanf("%d %d", &n, &k);
        memset(data, , sizeof(data));
        while (k--) {
            scanf(" %s", str);
            if (str[] == 'C') {
                int x1, x2, y1, y2;
                scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                Add(x1, y1, );
                Add(x2+, y1, );
                Add(x1, y2+, );
                Add(x2+, y2+, );
            }
            else {
                int x, y;
                scanf("%d %d", &x, &y);
                printf("%d\n", Sum(x, y)%);
            }
        }
        if (T)
            printf("\n");
    }
}