題目

https://vjudge.net/contest/225622#problem/A

題目大意

二維數(shù)組，初始為0，C操作區(qū)間更新，區(qū)間內(nèi)0變1，1變0；Q操作單點(diǎn)查詢

算法思路

• 這個(gè)區(qū)間更新并不用pushdown操作，pushup也不用，因?yàn)樗菃吸c(diǎn)查詢，只要在查詢時(shí)看對(duì)這個(gè)點(diǎn)的所有祖先節(jié)點(diǎn)的操作次數(shù)，為奇數(shù)則為1，否則為0。
• updatex的時(shí)候當(dāng)前區(qū)間在需要更新的區(qū)間內(nèi)，則updatey
• queryx當(dāng)前節(jié)點(diǎn)是需要查詢的節(jié)點(diǎn)的父節(jié)點(diǎn)時(shí)都要queryy一下。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
#define pb(x) push_back(x)
#define fir first
#define sec second
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int INF=0x3f3f3f3f;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
//ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);


const int maxn=1010;
int tree[maxn<<2][maxn<<2];
int n;
void updatey(int kx,int l,int r,int yl,int yr,int ky){
   if(yl<=l&&yr>=r){
     tree[kx][ky]=!tree[kx][ky];
     return;
   }
   int mid=(l+r)/2;
   if(mid>=yl) updatey(kx,l,mid,yl,yr,ky*2);
   if(mid<yr) updatey(kx,mid+1,r,yl,yr,ky*2+1);
}
void updatex(int l,int r,int xl,int xr,int yl,int yr,int kx){//xl,xr is fresh area
 if(xl<=l&&xr>=r){
    updatey(kx,1,n,yl,yr,1);
   return;
 }
 int mid=(l+r)/2;
 if(mid>=xl) updatex(l,mid,xl,xr,yl,yr,kx*2);
 if(mid<xr) updatex(mid+1,r,xl,xr,yl,yr,kx*2+1);
}

int queryy(int kx,int l,int r,int y,int ky){
   int cnt=0;
   if(tree[kx][ky]) cnt++;
   if(l==r) return cnt;
   int mid=(l+r)/2;
   if(y<=mid) cnt+=queryy(kx,l,mid,y,ky*2);
   else cnt+=queryy(kx,mid+1,r,y,ky*2+1);
   return cnt;
}
int queryx(int l,int r,int x,int y,int kx){
   int cnt=0;
   cnt+=queryy(kx,1,n,y,1);
   if(l==r) return cnt;
   int mid=(l+r)/2;
   if(x<=mid) cnt+=queryx(l,mid,x,y,kx*2);
   else cnt+=queryx(mid+1,r,x,y,kx*2+1);
   return cnt;
}


int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int x;
  cin>>x;
  while(x--){
    int t;
    cin>>n>>t;
   // cout<<n<<t<<endl;
    memset(tree,0,sizeof(tree));
    int cnt=0;
    for(int i=0;i<t;i++){
        //getchar();
        char ch;
        cin>>ch;
        if(ch=='C'){
               // cout<<ch<<endl;
                int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            updatex(1,n,x1,x2,y1,y2,1);
        }
        else if(ch=='Q'){
            int xx,y;
            cin>>xx>>y;
             if(queryx(1,n,xx,y,1)%2==0) cout<<0<<endl;
             else cout<<1<<endl;
        }
    }
    if(x) cout<<endl;
  }
}