poj2155 Matrix 树状数组套树状数组

Description

---

给定一些二维数组中的操作形如C x1 y1 x2 y2表示把(x1,y1)到(x2,y2)中的数字0变成1，1变成0，Q x y表示查询(x,y)

Solution

–

sb题，直接二维树状数组套树状数组。至于0还是1的问题可以看成操作了x次就是x%2，按照类似矩阵前缀和的方法更新

Code

---

#include <stdio.h>
#include <string.h>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
#define fill(x,t) memset(x,t,sizeof(x))
#define N 2005
int c[N][N];
int T,n,m;
void read(int &x) {
    x=0; char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar());
for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
}
int lowbit(int x) {return x&(-x);}
int query(int x,int y) {
int ret=0;
for (int i=x;i>0;i-=lowbit(i)) {
for (int j=y;j>0;j-=lowbit(j)) {
            ret+=c[i][j];
        }
    }
return ret&1;
}
void modify(int x,int y) {
for (int i=x;i<=n;i+=lowbit(i)) {
for (int j=y;j<=n;j+=lowbit(j)) {
            ++c[i][j];
        }
    }
}
int main(void) {
    read(T);
while (T--) {
        fill(c,0);
        read(n); read(m);
        rep(i,1,m) {
char opt=getchar();
int x1,y1,x2,y2;
            read(x1); read(y1);
if (opt=='Q') printf("%d\n",query(x1,y1));
else {
                read(x2); read(y2);
                modify(x1,y1);
                modify(x2+1,y1);
                modify(x1,y2+1);
                modify(x2+1,y2+1);
            }
        }
puts("");
    }
return 0;
}