如何选择品牌网站建设,wordpress 搜索不能用,广告设计是做什么,有多少网站可以推广业务正题
题目链接:https://www.luogu.org/problem/P3690 题目大意 nnn个点mmm个操作#xff0c;要求支持
询问路径异或和连接一条边(若x,yx,yx,y没联通)删除一条边修改一个点的权值 解题思路 LCTLCTLCT板子题不解释。 codecodecode
#includecstdio
#includecstrin…正题
题目链接:https://www.luogu.org/problem/P3690 题目大意
nnn个点mmm个操作要求支持
询问路径异或和连接一条边(若x,yx,yx,y没联通)删除一条边修改一个点的权值 解题思路
LCTLCTLCT板子题不解释。 codecodecode
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N3e5100;
int n,m,v[N];
struct Link_Cut_Tree{int w[N],fa[N],son[N][2];bool r[N];#define ls son[x][0]#define rs son[x][1]bool nroot(int x){return son[fa[x]][0]x||son[fa[x]][1]x;}void PushUp(int x){w[x]w[ls]^w[rs]^v[x];return;}void PushR(int x){swap(ls,rs);r[x]^1;return;}void PushDown(int x){if(r[x]){if(ls) PushR(ls);if(rs) PushR(rs);r[x]0;}return;}void Rotate(int x){int yfa[x],zfa[y],k(son[y][1]x),wson[x][!k];if(nroot(y)) son[z][son[z][1]y]x;son[x][!k]y;son[y][k]w;if(w) fa[w]y;fa[y]x;fa[x]z;PushUp(y);return;}void PushHall(int x){if(nroot(x)) PushHall(fa[x]);PushDown(x); return;}void Splay(int x){int yx,z0;PushHall(x);while(nroot(x)){yfa[x];zfa[y];if(nroot(y))Rotate((son[y][0]x)^(son[z][0]y)?x:y);Rotate(x);} PushUp(x);return;}void Access(int x){for(int y0;x;xfa[yx])Splay(x),rsy,PushUp(x);return;}void MakeRoot(int x){Access(x);Splay(x);PushR(x);return;}int FindRoot(int x){Access(x);Splay(x);while(ls) PushDown(x),xls;Splay(x);return x;}void Split(int x,int y){MakeRoot(x);Access(y);Splay(y);return;}void Link(int x,int y){MakeRoot(x);if(FindRoot(y)!x) fa[x]y;}void Cut(int x,int y){MakeRoot(x);if(FindRoot(y)xfa[y]x!son[y][0]){fa[y]son[x][1]0;PushUp(x);} }#undef ls#undef rs
}LCT;
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,v[i]);while(m--){int op,x,y;scanf(%d%d%d,op,x,y);if(op0){LCT.Split(x,y);printf(%d\n,LCT.w[y]);}if(op1){LCT.Link(x,y);}if(op2){LCT.Cut(x,y);}if(op3){LCT.Splay(x);v[x]y;}}
}
