[bzoj3282][LCT]Tree

2023-10-16 04:08

文章标签 tree lct bzoj3282

本文主要是介绍[bzoj3282][LCT]Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

Input

第１行两个整数,分别为Ｎ和Ｍ,代表点数和操作数。第２行到第Ｎ＋１行,每行一个整数,整数在［１,１０＾９］内,代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行,每行三个整数,分别代表操作类型和操作所需的量。１＜＝Ｎ，Ｍ＜＝３０００００

Output

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

Sample Input

3 3

1

2

3

1 1 2

0 1 2

0 1 1

Sample Output

3

1

题解

LCT维护一下树上异或和
弄个sum表示以i为根的子树的xor和
瞎搞一搞就好了
模板打错了T了三发。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct node
{int f,son[2],c,sum;bool reverse;node(){reverse=false;c=sum=0;}
}tr[310000];int n,m;
void reverse(int now)
{int lc=tr[now].son[0],rc=tr[now].son[1];swap(tr[now].son[0],tr[now].son[1]);tr[lc].reverse^=1;tr[rc].reverse^=1;tr[now].reverse=false;
}
void upd(int now){tr[now].sum=tr[tr[now].son[0]].sum^tr[tr[now].son[1]].sum^tr[now].c;}
void rotate(int x,int w)
{int R,r;int f=tr[x].f,ff=tr[f].f;R=f;r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff;r=x;if(tr[R].son[0]==f)tr[R].son[0]=r;else if(tr[R].son[1]==f)tr[R].son[1]=r;tr[r].f=R;R=x;r=f;tr[R].son[w]=r;tr[r].f=R;upd(f);upd(x);
}
int tmp[310000];
void splay(int x,int rt)
{int i=x,s=0;while(tr[i].f!=rt && (tr[tr[i].f].son[0]==i || tr[tr[i].f].son[1]==i)){tmp[++s]=i;i=tr[i].f;}tmp[++s]=i;while(s){i=tmp[s--];if(tr[i].reverse)reverse(i);}while(tr[x].f!=rt && (tr[tr[x].f].son[0]==x || tr[tr[x].f].son[1]==x)){int f=tr[x].f,ff=tr[f].f;if(ff==rt || (tr[ff].son[0]!=f && tr[ff].son[1]!=f)){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f && tr[f].son[0]==x)rotate(f,1),rotate(x,1);else if(tr[ff].son[1]==f && tr[f].son[0]==x)rotate(x,1),rotate(x,0);else if(tr[ff].son[1]==f && tr[f].son[1]==x)rotate(f,0),rotate(x,0);else rotate(x,0),rotate(x,1);}}
}
void access(int x)
{int y=0;while(x!=0){splay(x,0);tr[x].son[1]=y;if(y!=0)tr[y].f=x;y=x;x=tr[x].f;}
}
void markroot(int x){access(x);splay(x,0);tr[x].reverse^=1;}
void link(int x,int y){markroot(x);tr[x].f=y;access(x);}
int findroot(int x)
{access(x);splay(x,0);while(tr[x].son[0]!=0)x=tr[x].son[0];return x;
}
void cut(int x,int y)
{if(findroot(x)!=findroot(y))return ;markroot(x);access(y);splay(y,0);tr[tr[y].son[0]].f=0;tr[y].son[0]=0;
}
int findsum(int x,int y)
{markroot(x);access(y);splay(y,0);return tr[tr[y].son[0]].sum^tr[y].c;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&tr[i].c);tr[i].sum=tr[i].c;}while(m--){int op,x,y;scanf("%d%d%d",&op,&x,&y);if(op==0)printf("%d\n",findsum(x,y));else if(op==1){int tmpx=findroot(x);int tmpy=findroot(y);if(tmpx!=tmpy)link(x,y);}else if(op==2)cut(x,y);else{markroot(x);tr[x].c=y;upd(x);}}return 0;
}