树状数组 POJ-2155 Matrix

题目链接：[ POJ - 2155 ]

题目大意

对一个n∗n的矩阵：

1. 格式C x1 y1 x2 y2，表示将左上角为(x1,y1)，右下角为(x2,y2)的矩阵全部取反，即0变1，1变0.
2. Q x y，表示查询位置(x,y)的值.

设询问次数为t，则10^3, 1 ≤ t ≤ 10^5, 数据组数 ≤ 10.

题解

树状数组模板题，此题建立完整的二维树状数组板子

代码如下

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
using namespace std;

typedef long long ll;
ll a[1010][1010];
ll t, m, n;

inline ll lowbit(ll x)
{
    return x & -x;
}

ll sum(ll x, ll y)
{
    ll res = 0;
    for (ll i = x; i > 0; i -= lowbit(i))
       for (ll j = y; j > 0; j -= lowbit(j))
            res += a[i][j];
    return res;
}

void add(ll x, ll y, ll v)
{
    for (ll i = x; i <= n; i += lowbit(i))
        for (ll j = y; j <= n; j += lowbit(j))
            a[i][j] += v;
}

int main(void)
{
    cin >> t;
    while (t--) {
        memset(a, 0, sizeof(a));
        scanf("%lld%lld", &n, &m);
        getchar();

        char ch;
        ll x1, y1, x2, y2;
        while (m--) {
            scanf("%c %lld %lld", &ch, &x1, &y1);
            if (ch == 'Q') 
                printf("%lld\n", sum(x1, y1) % 2);

            if (ch == 'C') {
                scanf("%lld%lld", &x2, &y2);
                add(x1, y1, 1);
                add(x2 + 1, y1, 1);
                add(x1, y2 + 1, 1);
                add(x2 + 1, y2 + 1, 1);
            }
            getchar();
        }
        if (t)
            cout << endl;
    }

    return 0;
}