xfstart07
Get busy living or get busy dying

二维树状数组:
#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 阅读(119) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理