@zzzc18
2017-06-21T14:59:06.000000Z
字数 2371
阅读 1447
LCT
题目:洛谷模板题
#include<cstdio>
#include<algorithm>
#define MAXN 300005
using namespace std;
int n,m;
class Link_Cut_Tree{
public:
struct T_T{
int lazy,ls,rs,fa,val;
};
bool isroot(int x){
return !(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x);
}
void pushdown(int x){
if(tree[x].lazy){
tree[x].lazy=0;
tree[tree[x].ls].lazy^=1;
tree[tree[x].rs].lazy^=1;
swap(tree[x].ls,tree[x].rs);
}
}
void clean(){
tree[0].ls=tree[0].rs=tree[0].val=tree[0].lazy=0;
}
void rotate(int x){
int y=tree[x].fa,z=tree[y].fa;
if(tree[tree[y].fa].ls==y || tree[tree[y].fa].rs==y){
if(tree[z].ls==y)
tree[z].ls=x;
else
tree[z].rs=x;
}
tree[x].fa=z;
tree[y].fa=x;
if(tree[y].ls==x){
tree[tree[x].rs].fa=y;
tree[y].ls=tree[x].rs;
tree[x].rs=y;
}
else{
tree[tree[x].ls].fa=y;
tree[y].rs=tree[x].ls;
tree[x].ls=y;
}
up(y);up(x);
clean();
}
int que[MAXN];
void splay(int x){
int y,z;int top=1;
que[top]=x;
for(int i=x;!isroot(i);i=tree[i].fa)
que[++top]=tree[i].fa;
for(int i=top;i;i--)
pushdown(que[i]);
while(tree[tree[x].fa].ls==x||tree[tree[x].fa].rs==x){
y=tree[x].fa;z=tree[y].fa;
if(tree[tree[y].fa].ls==y||tree[tree[y].fa].rs==y){
if((tree[y].ls==x && tree[z].rs==y)||(tree[y].rs==x && tree[z].ls==y))
rotate(x);
else
rotate(y);
}
rotate(x);
}
}
T_T tree[MAXN];
//////////////////////////////////////////////////////////////////////////////////////////
int xr[MAXN];
void up(int x){
xr[x]=xr[tree[x].ls]^xr[tree[x].rs]^tree[x].val;
}
void access(int x){
int t=0;
while(x){
splay(x);
tree[x].rs=t;
up(x);
t=x;
x=tree[x].fa;
}
}
void makeroot(int x){
access(x);
splay(x);
tree[x].lazy^=1;
}
int F(int x){
access(x);
splay(x);
while(tree[x].ls)
x=tree[x].ls;
return x;
}
void spilt(int x,int y){
makeroot(x);
access(y);
splay(y);
}
void cut(int x,int y){
spilt(x,y);
if(tree[y].ls==x){
tree[y].ls=0;
tree[x].fa=0;
}
}
void link(int x,int y){
makeroot(x);
tree[x].fa=y;
}
void DEBUG(){
int k;
for(k=1;k<=n;k++){
printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa);
}
}
}LCT;
int main(){
freopen("LCT.in","r",stdin);
freopen("my.out","w",stdout);
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++){
scanf("%d",&LCT.xr[i]);
LCT.tree[i].val=LCT.xr[i];
}
for(i=1;i<=m;i++){
int opt,x,y;
scanf("%d",&opt);
scanf("%d%d",&x,&y);
if(opt==0){
LCT.spilt(x,y);
printf("%d\n",LCT.xr[y]);
}
if(opt==1){
int xx=LCT.F(x),yy=LCT.F(y);
//printf("%d %d\n",xx,yy);
if(xx!=yy)
LCT.link(x,y);
}
if(opt==2){
int xx=LCT.F(x),yy=LCT.F(y);
if(xx==yy)
LCT.cut(x,y);
}
if(opt==3){
LCT.access(x);
LCT.splay(x);
LCT.tree[x].val=y;
LCT.up(x);
}
//if(i%500==0)
//LCT.DEBUG();
}
return 0;
}