二维树状数组：
#include<iostream>
using namespace std;
int N,M;
int a[1010][1010];
char s[2];
int lowbit(int x){
return x&(x^(x-1));
}
void modify(int x,int y,int num)
{
for(int i=x;i;i-=lowbit(i))
for(int j=y;j;j-=lowbit(j))
a[i][j]+=num;
}
void insert()
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(x1>x2){ int tmp=x1; x1=x2; x2=tmp; }
if(y1>y2){ int tmp=y1; y1=y2; y2=tmp; }
modify(x2,y2,1);
modify(x1-1,y2,-1);
modify(x2,y1-1,-1);
modify(x1-1,y1-1,1); //求矩阵和
}
int sum(int x,int y){
int tmp=0;
for(int i=x;i<=N;i+=lowbit(i))
for(int j=y;j<=N;j+=lowbit(j))
tmp+=a[i][j];
return tmp;
}
void updata()
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",sum(x,y)&1);
}
int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&N,&M);
memset(a,0,sizeof(a));
while(M--){
scanf("%s",s);
if(s[0]=='C') insert();
else updata();
}
printf("\n");
}
return 0;
}
posted on 2009-06-28 01:08
xfstart07 阅读(129)
评论(0) 编辑 收藏 引用