poj - 2155 - Matrix(树状数组)

题意:对于一个N*N的矩阵(2 <= N <= 1000),其中的元素初始为0,执行2种操作,一:C x1 y1 x2 y2——>对矩阵(x1, y1, x2, y)的所有元素求反(0——>1, 1——>0),二:Q x y——>问元素(x, y)的值。

题目链接:http://poj.org/problem?id=2155

——>>好题,好题。。。一般我们都能想到,只要知道位置(x, y)被翻的次数就行。。。对于一个二维区间的修改,我们可以只修改其左闭右开区间的端点。

原理:若其中修改为区间[x1, x2],其左闭右开区间为[x1, x2+1),只在x1和x2+1的位置执行翻转,那么,如果询问x1之前的,本来就没什么修改;如果询问[x1, x2]的,修改了一次,正确;如果询问[x2+1, +oo)的,修改为2次,偶数次修改值不变,正确。

——>>所以,这里只要修改4个点的值,(x1, y1)(修改), (x1, y2+1)(把值变回去), (x2+1, y1)(把值变回去), (x2+1, y2+1)(把值变回去)。。。#^_^。。。

。。。一不小心,让那个空行要求。。。PE了一次。。。T_T~

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 1000 + 10;

int N;
int c[maxn][maxn];

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

void add(int x1, int y1, int x2, int y2) {
    for(int i = x1; i <= N; i += lowerbit(i))
        for(int j = y1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x1; i <= N; i += lowerbit(i))
        for(int j = y2+1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x2+1; i <= N; i += lowerbit(i))
        for(int j = y1; j <= N; j += lowerbit(j))
            c[i][j]++;
    for(int i = x2+1; i <= N; i += lowerbit(i))
        for(int j = y2+1; j <= N; j += lowerbit(j))
            c[i][j]++;
}

int query(int x, int y) {
    int ret = 0;
    for(int i = x; i > 0; i -= lowerbit(i))
        for(int j = y; j > 0; j -= lowerbit(j))
            ret += c[i][j];
    return ret % 2;
}

int main()
{
    int X, T, x1, y1, x2, y2;
    char op;
    scanf("%d", &X);
    while(X--) {
        scanf("%d%d", &N, &T);
        memset(c, 0, sizeof(c));
        while(T--) {
            getchar();
            op = getchar();
            if(op == ‘C‘) {
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1, x2, y2);
            }
            else {
                scanf("%d%d", &x1, &y1);
                printf("%d\n", query(x1, y1));
            }
        }
        if(X) puts("");
    }
    return 0;
}


poj - 2155 - Matrix(树状数组)

上一篇:数学之路-群体行为与群体智能(7)


下一篇:UVa10665 Diatribe against Pigeonholes