poj2155二维树状数组区间更新

时间:2021-03-14 15:36:51

垃圾poj又交不上题了,也不知道自己写的对不对

/*
给定一个矩阵,初始化为0:两种操作
第一种把一块子矩阵里的值翻转:0->1,1->0
第二种询问某个单元的值
直接累计单元格被覆盖的次数,如果被覆盖奇数次就是1,被覆盖偶数次就是0
树状数组解区间更新。。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1005
int bit[maxn][maxn],n,q;
void add(int x,int y,int num){
for(int i=x;i<=n;i+=i&-i)
for(int j=y;j<=n;j+=j&-j)
bit[i][j]+=num;
}
int query(int x,int y){
int res=;
for(int i=x;i;i-=i&-i)
for(int j=y;j;j-=j&-j)
res+=bit[i][j];
return res;
}
int main(){
int t,x1,x2,y1,y2;
char op[];
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&q);
while(q--){
scanf("%s",&op);
if(op[]=='C'){
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
add(x1,y1,);add(x1,y2+,);
add(x2+,y1,);add(x2+,y2+,);
}
else {
scanf("%d%d",&x1,&y1);
printf("%d\n",query(x1,y1)%);
}
}
printf("\n");
}
}