POJ2155 Matrix(二维树状数组)

题目传送门:http://poj.org/problem?id=2155

这道题要求区间修改,单点查询,可以用类似差分的方法转化为单点修改,区间查询。对于翻转操作X1,Y1,X2,Y2,只要把(X1,Y1),(X1,Y2+1),(X2+1,y1),(X2+1,Y2+1)四个点的值^=1,询问时只需求左上角为(1,1),右下角为(X,Y)的矩阵的值的异或和,及模2意义下的数和。用二维树状数组就可以维护。

code:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
int T,n,m,a,b,c,d,t[1005][1005];
char ch[1];
int lowbit(int x){
    return x&-x;
}
void modify(int x,int y,int z){
    for(int i=x;i<=n;i+=lowbit(i))
        for(int j=y;j<=n;j+=lowbit(j))
            t[i][j]+=z;
}
int sum(int x,int y){
    int s=0;
    for(int i=x;i;i-=lowbit(i))
        for(int j=y;j;j-=lowbit(j))
            s+=t[i][j];
    return s;
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                t[i][j]=0;
        while(m--){
            scanf("%s",ch);
            if(ch[0]=='Q'){
                scanf("%d%d",&a,&b);
                printf("%d\n",sum(a,b)&1);
            }
            else{
                scanf("%d%d%d%d",&a,&b,&c,&d);
                modify(a,b,1);
                modify(a,d+1,1);
                modify(c+1,b,1);
                modify(c+1,d+1,1);
            }
        }
        printf("\n");
    }
    return 0;
}

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注