POJ2155 Matrix(二维树状数组)

February 15, 2016

题目链接

题意:矩阵默认全为 0,操作是对输入的两个点构成的矩形内所有元素取反,询问是问某个点是 1 还是 0。

二维树状数组解决此题非常巧妙,更新矩形四个顶点。

如果想不明白的话,可以先考虑一维的情况:对[x, y] 区间内所有数取反,可以看成对树状数组的 a[ x ]和 a[ y+1 ]加一。

详解建议参考:浅谈信息学竞赛中的“0”和“1”

#include<iostream>
#include<cmath>
#include<queue>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<set>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int a[1010][1010];
int lowbit(int x){
    return x&(-x);
}
void add2(int x,int y,int num){//二维
    for(int i = x; i <= n; i += lowbit(i))
        for(int j = y; j <= n; j += lowbit(j))
            a[i][j] += num;
}
int sum2(int x,int y){
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i))
        for(int j = y; j > 0; j -= lowbit(j))
            res += a[i][j];
    return res;
}
int main(){
    //freopen("a.txt", "r", stdin);
    int T, x1, y1, x2, y2, m; cin >>T;
    char s[5];
    while(T--){
        memset(a, 0, sizeof(a));
        scanf("%d%d", &n, &m);
        while(m--){
            scanf("%s", s);
            if(s[0] == 'C'){
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add2(x1, y1, 1);
                add2(x2+1, y2+1, 1);
                add2(x1, y2+1, 1);
                add2(x2+1, y1, 1);
            }else{
                scanf("%d%d", &x1, &y1);
                printf("%dn", sum2(x1,y1)%2);
            }
        }
        cout <<endl;
    }
    return 0;
}

Profile picture

Written by Armin Li , a venture capitalist. [Weibo] [Subscribe]