粘板子：
文章图片
文章图片
#include#include #include using namespace std; const int N = 300050; template inline void read(T&x) { T f = 1,c = 0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0'; ch=getchar(); } x = f*c; } int n,m,val[N]; struct LCT { int fa[N],ch[N][2],w[N],v[N]; bool res[N]; inline void rever(int u){swap(ch[u][0],ch[u][1]); res[u]^=1; } inline bool isroot(int u){return ch[fa[u]][0]!=u&&ch[fa[u]][1]!=u; } inline void update(int u){w[u]=w[ch[u][0]]^w[ch[u][1]]^v[u]; } inline void pushdown(int u) { if(!u)return ; if(res[u]) { rever(ch[u][0]); rever(ch[u][1]); res[u]=0; } } void rotate(int x) { int y = fa[x],z = fa[y],k = (ch[y][1]==x); if(!isroot(y))ch[z][ch[z][1]==y]=x; fa[x] = z; ch[y][k] = ch[x][!k],fa[ch[x][!k]] = y; ch[x][!k] = y,fa[y] = x; update(y),update(x); } void down(int x) { if(!isroot(x))down(fa[x]); pushdown(x); } void splay(int x) { down(x); while(!isroot(x)) { int y = fa[x],z = fa[y]; if(!isroot(y)) (ch[z][1]==y)^(ch[y][1]==x)?rotate(x):rotate(y); rotate(x); } } void access(int x) { int y = 0; while(x) { splay(x); ch[x][1]=y; update(x); y=x,x=fa[x]; } } void mtr(int x) { access(x); splay(x); rever(x); } int get_root(int x) { access(x); splay(x); while(ch[x][0])x=ch[x][0]; return x; } void link(int x,int y) { mtr(x); if(get_root(y)!=x)fa[x]=y; } void cut(int x,int y) { mtr(x); access(y),splay(y); if(ch[y][0]==x) { ch[y][0]=fa[x]=0; update(y); } } void insert(int x,int y) { splay(x); v[x]=y; update(x); } int query(int x,int y) { mtr(x); access(y); splay(y); return w[y]; } }tr; int main() { read(n),read(m); for(int i=1; i<=n; i++)read(val[i]),tr.v[i]=tr.w[i]=val[i]; for(int op,x,y,i=1; i<=m; i++) { read(op),read(x),read(y); if(op==0)printf("%d\n",tr.query(x,y)); else if(op==1)tr.link(x,y); else if(op==2)tr.cut(x,y); else tr.insert(x,y); } return 0; }
View Code
【LCT板子】转载于:https://www.cnblogs.com/LiGuanlin1124/p/11161755.html
