题目背景
动态树
题目描述
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
输入输出格式
输入格式：
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
输出格式：
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
输入输出样例
输入样例#1：
3 3 1 2 3 1 1 2 0 1 2 0 1 1
输出样例#1：
3 1
说明
数据范围： N,M<=3*10^5.
课上听老师讲的还蛮有道理的，然而调起来简直想打人hhh
不能完全按照splay的套路写。。例如以下的这个错误我调了一个点(...):
我写splay的时候rotate直接判断grandfather(x)如果是0的话就不用连x了，
但是当LCT这么写(我一开始改的是!isroot(fa),但是此时fa的father已经变了，所以gg)会挂。
得改成 if(ch[ffa][0]==fa||ch[ffa][1]==fa) then (balabla)
诸如此类的细节还有很多，，，反正多写写把。。。晚上再搞一道熟练熟练。
/* 若干splay维护树(森林)中的重链 每颗splay的中序遍历恰好是一条重链 从上走到下。 一个节点最多只能有一个偏爱儿子， 所以在access的时候要先把当前点旋到splay的根， 把右儿子(也就是在树中的偏爱儿子)断掉， 换成到access的点路径上的儿子。 */ #include<bits/stdc++.h> #define maxn 300005 using namespace std; int n,m,val[maxn],opt,a,b; struct LCT{ int len,ch[maxn][2],f[maxn]; int tag[maxn],xr[maxn],q[maxn]; inline void init(){ memset(f,0,sizeof(f)); memset(ch,0,sizeof(ch)); memset(tag,0,sizeof(tag)); } //更新节点信息 inline void update(int x){ xr[x]=xr[ch[x][0]]^xr[ch[x][1]]^val[x]; } //标记下传 inline void pushdown(int x){ if(tag[x]){ tag[x]=0,tag[ch[x][0]]^=1,tag[ch[x][1]]^=1; swap(ch[x][0],ch[x][1]); } } inline int get(int x){ return ch[f[x]][1]==x; } //判断一个节点是否为当前splay的根 inline bool isroot(int x){ return (ch[f[x]][0]!=x&&ch[f[x]][1]!=x); } //splay的旋转操作 inline void rotate(int x){ int fa=f[x],ffa=f[fa],tp=get(x); ch[fa][tp]=ch[x][tp^1],f[ch[fa][tp]]=fa; ch[x][tp^1]=fa,f[fa]=x; f[x]=ffa; if(ch[ffa][0]==fa||ch[ffa][1]==fa) ch[ffa][ch[ffa][1]==fa]=x; update(fa),update(x); } //旋到根 inline void splay(int x){ len=0; for(int i=x;;i=f[i]){ q[++len]=i; if(isroot(i)) break; } for(;len;len--) pushdown(q[len]); while(!isroot(x)){ int y=f[x],z=f[y]; if(!isroot(y)) rotate((get(y)==get(x)?y:x)); rotate(x); } } //将一个点到它所在的树的根的路径上的边都变成重边 inline void access(int x){ for(int son=0;x;son=x,x=f[x]) splay(x),ch[x][1]=son,update(x); } //把一个节点搞成它所在树的根 inline void makeroot(int x){ access(x); splay(x),tag[x]^=1; } //找所在树的根 inline int find_root(int x){ access(x),splay(x); while(ch[x][0]) x=ch[x][0]; return x; } //把y所在的树从y点接到x点上 inline void add(int x,int y){ makeroot(x),f[x]=y; //不能更新，因为y不是x的重儿子 } //把x和y点断开 inline void cut(int x,int y){ makeroot(x),access(y); splay(y); if(ch[y][0]==x) ch[y][0]=0,f[x]=0; } }M; int main(){ M.init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",val+i),M.xr[i]=val[i]; while(m--){ scanf("%d%d%d",&opt,&a,&b); if(!opt){ M.makeroot(a),M.access(b),M.splay(b); printf("%d ",M.xr[b]); } else if(opt==1){ if(M.find_root(a)==M.find_root(b)) continue; M.add(a,b); } else if(opt==2){ if(M.find_root(a)!=M.find_root(b)) continue; M.cut(a,b); } else{ M.access(a),M.splay(a); val[a]=b,M.update(a); } } return 0; }