POJ 2155(Matrix)非常规思路

spoiler posted @ 2011年4月11日 19:44 in 树状数组经典题目 , 1354 阅读

颠覆树状数组的常规模式,这题有些地方还有疑点!关于怎么计算点的翻转次数,为什么是他前面比他大的个数呢?回来再好好想想!
#include<iostream>
#include<stdio.h>
#include<string.h>
#define N 2001
#define lowbit(x)  (x&(-x))
using namespace std;

int c[N][N];

int UPdate(int x,int y,int num){
int k;
while(x>0){
  k=y;
  while(k>0){
   c[x][k]^=num;
   k-=lowbit(k);
  }
  x-=lowbit(x);
}
return 0;
}

int getsum(int x,int y){
int sum=0,k;
while(x<=N){
  k=y;
  while(k<=N){
   sum^=c[x][k];
   k+=lowbit(k); 
  }
  x+=lowbit(x);
}
return sum;
}

int main(){
int cas,i,n,q;
int x1,x2,y1,y2;
char sign;
cin>>cas;
while(cas--){
  memset(c,0,sizeof(c));
  scanf("%d %d",&n,&q);
  while(q--){
   cin>>sign;
   //getchar();
   if(sign=='C'){
    cin>>x1>>y1>>x2>>y2;
    x1++; x2++; y1++; y2++;
    //printf("%d %d %d %d",x1,y1,x2,y2);
    UPdate(x2,y2,1); UPdate(x1-1,y2,1);
    UPdate(x2,y1-1,1); UPdate(x1-1,y1-1,1);
   }
   if(sign=='Q'){
    scanf("%d %d",&x1,&y1);
    x1++;   y1++;
    printf("%d\n",1&getsum(x1,y1));
   }
  }
  printf("\n");
}
return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter