因为最近准备模板,所以把不太常用的算法又熟悉了一边,发现果然不练不行。
二维线段树,树套树
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
int n,m;
struct nodey
{
int l,r,num;
};
struct nodex
{
int l,r;
nodey y[1005<<2];
}tree[1005<<2];
void buildy(int l,int r,int pos,int now)
{
tree[pos].y[now].l=l;
tree[pos].y[now].r=r;
tree[pos].y[now].num=0;
if(l==r)return ;
int mid=(l+r)>>1;
buildy(l,mid,pos,now<<1);
buildy(mid+1,r,pos,now<<1|1);
}
void buildx(int l,int r,int now)
{
tree[now].l=l;
tree[now].r=r;
buildy(1,n,now,1);
if(l==r)return ;
int mid=(l+r)>>1;
buildx(l,mid,now<<1);
buildx(mid+1,r,now<<1|1);
}
void queryy(int pos,int y,int now,int &t)
{
//cout<<tree[pos].l<<" "<<tree[pos].r<<" "<<tree[pos].y[now].l<<" "<<tree[pos].y[now].r<<" "<<tree[pos].y[now].num<<endl;
t^=tree[pos].y[now].num;
if(tree[pos].y[now].l==tree[pos].y[now].r)
return ;
int mid=(tree[pos].y[now].l+tree[pos].y[now].r)>>1;
if(y<=mid)
queryy(pos,y,now<<1,t);
else
queryy(pos,y,now<<1|1,t);
}
void queryx(int x,int y,int now,int &t)
{
queryy(now,y,1,t);
if(tree[now].l==tree[now].r)
return ;
int mid=(tree[now].l+tree[now].r)>>1;
if(x<=mid)
queryx(x,y,now<<1,t);
else
queryx(x,y,now<<1|1,t);
}
void updatey(int y1,int y2,int pos,int now)
{
if(tree[pos].y[now].l==y1 && tree[pos].y[now].r==y2)
{
// cout<<"1";
// tree[pos].y[now].num++;
tree[pos].y[now].num=!tree[pos].y[now].num;
return ;
}
int mid=(tree[pos].y[now].l+tree[pos].y[now].r)>>1;
if(y2<=mid)
updatey(y1,y2,pos,now<<1);
else if(y1>mid)
updatey(y1,y2,pos,now<<1|1);
else
{
updatey(y1,mid,pos,now<<1);
updatey(mid+1,y2,pos,now<<1|1);
}
}
void updatex(int x1,int y1,int x2,int y2,int now)
{
if(tree[now].l==x1 && tree[now].r==x2)
{
updatey(y1,y2,now,1);
return ;
}
int mid=(tree[now].l+tree[now].r)>>1;
if(x2<=mid)
updatex(x1,y1,x2,y2,now<<1);
else if(x1>mid)
updatex(x1,y1,x2,y2,now<<1|1);
else
{
updatex(x1,y1,mid,y2,now<<1);
updatex(mid+1,y1,x2,y2,now<<1|1);
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
buildx(1,n,1);
while(m--)
{
char ch[5];
int a,b,c,d;
scanf("%s",ch);
if(ch[0]=='C')
{
scanf("%d%d%d%d",&a,&b,&c,&d);
updatex(a,b,c,d,1);
/* for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
cout<<tree[j].y[i].num<<" ";
}
cout<<endl;
}*/
}
else
{
scanf("%d%d",&a,&b);
int temp=0;
queryx(a,b,1,temp);
printf("%d\n",temp);
}
}
cout<<endl;
}
return 0;
}