題目背景 動態樹 題目描述 給定n個點以及每個點的權值，要你處理接下來的m個操作。操作有4種。操作從0到3編號。點從1到n編號。 0：後接兩個整數(x，y)，代表詢問從x到y的路徑上的點的權值的xor和。保證x到y是聯通的。 1：後接兩個整數(x，y)，代表連接x到y，若x到y已經聯通則無需連接。 ...
題目背景
動態樹
題目描述
給定n個點以及每個點的權值，要你處理接下來的m個操作。操作有4種。操作從0到3編號。點從1到n編號。
0：後接兩個整數(x，y)，代表詢問從x到y的路徑上的點的權值的xor和。保證x到y是聯通的。
1：後接兩個整數(x，y)，代表連接x到y，若x到y已經聯通則無需連接。
2：後接兩個整數(x，y)，代表刪除邊(x，y)，不保證邊(x，y)存在。
3：後接兩個整數(x，y)，代表將點x上的權值變成y。
輸入輸出格式
輸入格式：
第1行兩個整數，分別為n和m，代表點數和操作數。
第2行到第n+1行，每行一個整數，整數在［1，10^9］內，代表每個點的權值。
第n+2行到第n+m+1行，每行三個整數，分別代表操作類型和操作所需的量。
輸出格式：
對於每一個0號操作，你須輸出x到y的路徑上點權的xor和。
輸入輸出樣例
輸入樣例#1： 複製3 3 1 2 3 1 1 2 0 1 2 0 1 1輸出樣例#1： 複製
3 1
說明
數據範圍： 1 \leq N, M \leq 3 \cdot {10}^51≤N,M≤3⋅105
看了一下午的講解
看了一晚上的代碼
算是差不多理解了，不過還有一個潛在的隱患沒有解決，就是代碼里那個玄學的pushdown函數
等搞懂了再整理吧
// luogu-judger-enable-o2 // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=3 * 1e5 + 10; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();} return x * f; } #define fa(x) T[x].f #define ls(x) T[x].ch[0] #define rs(x) T[x].ch[1] int v[MAXN]; struct node { int f, ch[2], s; bool r; }T[MAXN]; int ident(int x) { return T[fa(x)].ch[0] == x ? 0 : 1;//判斷該節點是父親的哪個兒子 } int connect(int x,int fa,int how) { T[x].f=fa; T[fa].ch[how]=x;//連接 } inline bool IsRoot(int x) {//若為splay中的根則返回1 否則返回0 return ls( fa(x) ) != x && rs( fa(x) ) != x; //用到了兩個性質 //1.若x與fa(x)之間的邊是虛邊，那麼它的父親的孩子中不會有他（不在同一個splay內） //2. splay的根節點與其父親之間的邊是虛邊 } void update(int x) { T[x].s = T[ls(x)].s ^ T[rs(x)].s ^ v[x];//維護路徑上的異或和 } void pushdown(int x) { if(T[x].r) { swap(ls(x),rs(x)); T[ls(x)].r ^= 1; T[rs(x)].r ^= 1; T[x].r = 0;//標記下傳 } } void rotate(int x) { int Y = T[x].f, R = T[Y].f, Yson = ident(x), Rson = ident(Y); int B = T[x].ch[Yson ^ 1]; //Q為什麼要這樣寫 ******************************************** T[x].f = R; if(!IsRoot(Y)) connect(x, R, Rson); //這裡如果不判斷y是否根節點，那麼當y是根節點的時候，0節點的兒子就會被更新為x //這樣x就永遠不能被判斷為根節點，也就會無限迴圈下去了 //但是這裡不更新x的父親的話就會出現無限遞歸的情況 connect(B, Y, Yson); connect(Y, x, Yson ^ 1); update(Y); update(x); } int st[MAXN]; void splay(int x) { int y = x, top = 0; st[++top] = y; while(!IsRoot(y)) st[++top] = y = fa(y); while(top) pushdown(st[top--]); //因為在旋轉的時候不會處理標記，所以splay之前應該下傳所有標記 for(int y = fa(x); !IsRoot(x); rotate(x), y = fa(x))//只要不是根就轉 if(!IsRoot(y)) rotate( ident(x) == ident(y) ? x : y ); } void access(int x) {//訪問x節點 for(int y = 0; x; x = fa(y = x)) splay(x), rs(x) = y, update(x); //首先把x splay到所在平衡樹的根，這樣可以保證它的右孩子就是在原樹中對應的重鏈(右孩子深度比它大) //y是splay中x的兒子，把x的右兒子改成y，也就是把x和y之間的邊變成實邊 //更改了節點順序，需要update } void makeroot(int x) {//把x改為原樹的根節點 access(x); splay(x); T[x].r ^= 1; pushdown(x); //首先訪問一下x，再把x轉到根， //註意在access的時候都是連接的右兒子，這樣會破壞順序，因此我們需要將左右兒子翻轉 } int findroot(int x) {//找到x在原樹中的根節點 access(x);splay(x); while(ls(x)) x = ls(x);//找到深度最小的點即為根節點 return x; } void split(int x, int y) { makeroot(x);//首先把x置為根節點 access(y); splay(y); //然後訪問一下y，再把y轉到根節點，這樣y維護的就是x - y 路徑上的xor } void link(int x, int y) { makeroot(x);//把x置為根節點 if(findroot(y) != x ) fa(x) = y; //如果x與y不在同一個splay中，就把y置為x的父親 //因為不能判斷x與y的深度，因此在這裡不用更新y的兒子 } void cut(int x, int y) { makeroot(x); if(findroot(y) == x && fa(x) == y && !rs(x)) { fa(x) = T[y].ch[0] = 0; update(y); } //註意findroot(y)之後，y會成為根節點 //對於第三個判斷 //可以構造出這樣的樹 // x // fuck // y //在splay中是這樣的 // y //x // fuck //這樣很顯然x與y是不相連的 } int main() { #ifdef WIN32 freopen("a.in","r",stdin); //freopen("a.out","w",stdout); #else #endif int N = read(), M = read(); for(int i = 1; i <= N; i++) v[i] = read(); for(int i = 1; i <= M; i++) { int opt = read(), x = read(), y = read(); if(opt == 0) split(x, y), printf("%d\n",T[y].s); else if(opt == 1) link(x, y); else if(opt == 2) cut(x, y); else if(opt == 3) splay(x), v[x] = y; } return 0; }
