题目描述
给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。
０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。
１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。
２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。
３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。
输入
第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。
第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。
第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。
输出
对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。
样例输入
3 3
1 2 3 1 1 2 0 1 2 0 1 1样例输出
3
1题解
真正的LCT模板题，几乎包括了LCT所有基本操作
#include#include #define N 300010#define lson c[0][x]#define rson c[1][x]using namespace std;int fa[N] , c[2][N] , w[N] , sum[N] , rev[N];char str[5];void pushup(int x){ sum[x] = sum[lson] ^ sum[rson] ^ w[x];}void pushdown(int x){ if(rev[x]) { swap(c[0][lson] , c[1][lson]); swap(c[0][rson] , c[1][rson]); rev[lson] ^= 1 , rev[rson] ^= 1; rev[x] = 0; }}bool isroot(int x){ return c[0][fa[x]] != x && c[1][fa[x]] != x;}void update(int x){ if(!isroot(x)) update(fa[x]); pushdown(x);}void rotate(int x){ int y = fa[x] , z = fa[y] , l = (c[1][y] == x) , r = l ^ 1; if(!isroot(y)) c[c[1][z] == y][z] = x; fa[x] = z , fa[y] = x , fa[c[r][x]] = y , c[l][y] = c[r][x] , c[r][x] = y; pushup(y) , pushup(x);}void splay(int x){ update(x); while(!isroot(x)) { int y = fa[x] , z = fa[y]; if(!isroot(y)) { if((c[0][y] == x) ^ (c[0][z] == y)) rotate(x); else rotate(y); } rotate(x); }}void access(int x){ int t = 0; while(x) splay(x) , rson = t , pushup(x) , t = x , x = fa[x];}void makeroot(int x){ access(x) , splay(x); swap(lson , rson) , rev[x] ^= 1;}int find(int x){ access(x) , splay(x); while(lson) pushdown(x) , x = lson; return x;}void link(int x , int y){ makeroot(x) , fa[x] = y;}void cut(int x , int y){ makeroot(x) , access(y) , splay(y); if(c[0][y] == x && c[1][x] == 0) fa[x] = c[0][y] = 0 , pushup(y);}void split(int x , int y){ makeroot(y) , access(x) , splay(x);}int main(){ int n , m , i , p , x , y; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &w[i]) , sum[i] = w[i]; while(m -- ) { scanf("%d%d%d" , &p , &x , &y); switch(p) { case 0: split(x , y) , printf("%d\n" , sum[x]); break; case 1: if(find(x) != find(y)) link(x , y); break; case 2: cut(x , y); break; default: split(x , x) , w[x] = y , pushup(x); } } return 0;}