LCT 小記
這次不是整活了，記個筆記，加深下印象。
\(\text{1. LCT}\) 引入
題目描述
給定 \(n\) 個點以及每個點的權值，要你處理接下來的 \(m\) 個操作。
操作有四種，操作從 \(0\) 到 \(3\) 編號。點從 \(1\) 到 \(n\) 編號。
0 x y代表詢問從 \(x\) 到 \(y\) 的路徑上的點的權值的 \(\text{xor}\) 和。保證 \(x\) 到 \(y\) 是聯通的。1 x y代表連接 \(x\) 到 \(y\)，若 \(x\) 到 \(y\) 已經聯通則無需連接。2 x y代表刪除邊 \((x,y)\)，不保證邊 \((x,y)\) 存在。3 x y代表將點 \(x\) 上的權值變成 \(y\)。
動態樹問題，我們可以用 \(\text{LCT}\) 進行解決，這是一類問題，而不是某個單獨的數據結構。
\(\text{2. LCT}\) 相關定義
實鏈剖分
我們回顧以往遇到樹鏈問題的常用解決方法：樹鏈剖分。
樹鏈剖分實質上依賴於重鏈剖分，而 \(\text{LCT}\) 依賴於實鏈剖分。
實鏈剖分劃分出的邊叫實邊和虛邊。
對於每個節點它最多只能向一個兒子延申一條實邊，不是實邊的邊被定義為虛邊。
實邊的劃分相對自由，可以任意選擇一個兒子作為實邊。
由上面幾句話可自行歸納出一些關於實鏈剖分的事：
\(1.\) 實鏈與另一條實鏈之間由虛邊連接
\(2.\) 節點 \(x\) 最多只會向眾多兒子連一條實邊，其他兒子和 \(x\) 間均為虛邊
\(3.\) 節點 \(x\) 最多只會連一條實邊，也可以不連實邊
類比樹剖和實邊定義就可。
例如下圖中，有兩條實鏈 \(\{ 1 \rightarrow 3 \rightarrow 6\}\) 和 \(\{ 2 \rightarrow 4 \rightarrow 8 \}\) 。
實邊的選擇是很自由的，也可令 \(1 \rightarrow 3\) 的這條邊不為實邊，反而令 \(1 \rightarrow 2\) 為實邊，則其他邊不動的情況下，實鏈變為了 \(\{1 \rightarrow 2 \rightarrow 4 \rightarrow 8 \}\) 和 \(\{ 3 \rightarrow 6\}\)
維護方式
因為虛實邊的劃分是動態的，所以採用了靈活的 \(\text{spaly}\) 維護，而不能使用靜態的數據結構類似線段樹之類的。
可以用 \(\text{fhq treap}\) 寫，不過貌似會多個 \(\log\) 。
\(\text{LCT}\) 中的 \(\text{splay}\) 維護的是實鏈，要求 \(\text{splay}\) 的中序遍歷為自頂向下的實鏈。
注意這裡一個單獨的點也被 \(\text{splay}\) 維護着，因為伴隨着實邊虛邊的劃分，這個點可能成為實鏈中的一部分。
另外地，一個點只可能存在於一個 \(\text{splay}\) 中。
下圖展示了圖中樹 \(\text{splay}\) 所維護的鏈：
因為一條實鏈被一個 \(\text{splay}\) 所維護着，又因為一條實鏈與一條實鏈之間由虛邊連接。
所以變相的說，一個 \(\text{splay}\) 和另一個 \(\text{splay}\) 之間由虛邊連接。
然後 \(\text{splay}\) 由深度更大的指向深度小的，而不將深度小的指向深度大的，理由很顯然。
\(\text{3. LCT}\) 操作
首先需要申明自己的結構體，不然別人看不懂。
struct node {
int ch[2], fa, val, sum, tag;
//ch[0/1] 表示左兒子還是右兒子
//fa 表示父親
//val 表示當前節點權值
//sum 表示子樹權值
//tag 表示翻轉等操作要用的懶標記
} s[N];
\(\text{splay}\) 中的改動函數
上文中我們發現在 \(\text{LCT}\) 中 \(\text{splay}\) 的父親關係與普通的 \(\text{splay}\) 有所不同。
對於父親的判斷上，我們不僅需要判斷他是他父親的左兒子還是右兒子，還需要判斷他是否為一條實鏈的根節點。
判斷的方式利用之前提到的，深度小的 \(\text{splay}\) 不會指向深度大的 \(\text{splay}\) ，判斷他的父親的左右兒子中是否有他，如果沒有則為一條實鏈頂端。
int chk(int k) {
if(s[ s[k].fa ].ch[0] == k) return 0; // 表示是左兒子
if(s[ s[k].fa ].ch[1] == k) return 1; // 表示是右兒子
return -1; //表示是鏈頂端
}
同理的 \(\text{rotate}\) 和 \(\text{splay}\) 函數也有一點小的改動：
void connect(int k,int fa,int op) {
s[k].fa = fa;
if(op == 1) s[fa].ch[1] = k;
if(op == 0) s[fa].ch[0] = k;
}
void rotate(int x) {
int y = s[x].fa, z = s[y].fa;
int sx = chk(x), sy = chk(y), u = 0;
if(sx == 1) u = s[x].ch[0];//改動在這裡
if(sx == 0) u = s[x].ch[1];//改動在這裡
connect(u, y, sx); connect(y, x, sx ^ 1); connect(x, z, sy);
//改動在這裡
pushup(y); pushup(x);
}
void splay(int k) {
while( chk(k) != - 1 ) { //改為判斷是否轉到了鏈頂端
int y = s[k].fa;
if(chk(y) == -1) rotate(k); //只能轉一次
else if(chk(y) == chk(k)) rotate(y), rotate(k);
else rotate(k), rotate(k);
}
}
\(\text{LCT}\) 中的 \(\text{access}\) 操作
這個操作是 \(\text{LCT}\) 強大功能的基礎，\(\text{access(x)}\) 表示將整棵樹的根到 \(x\) 的路徑變為實鏈。
如下圖，我們要執行 \(\text{access(6)}\) 。
則執行完後的圖長這樣：
對於這條路徑的處理，首先我們要將路徑末的節點上連接的實邊全部換為虛邊，因為 \(\text{access}\) 求出的 \(1 \rightarrow 6\) 的路徑，如果下面還有實邊，則會變為 \(1 \rightarrow 7\) 的路徑。
同時對於路徑上的虛邊，要將它變為實邊，再將他所連接的父親本來所連接的實邊換為虛邊。
假設我們在執行 \(\text{access(x)}\) 操作。
這個的執行過程很簡單，考慮對 \(x\) 到根節點的鏈從下往上考慮。
對於每個點，先將他轉到他所在的 \(\text{splay}\) 的根節點。
然後每次改變他的右兒子的值為他下面的那個節點，如果是最底層節點則設為 \(0\) 。
因為是他的下層節點，我們都知道的，每個 \(\text{splay}\) 的中序遍歷是自頂向下的實鏈，那麼在下層的節點在 \(\text{splay}\) 中就處於右邊。
對於這個操作重複執行就可了。
複雜度是 \(\log n\) 的， \(\text{splay}\) 可以讓樹高均攤下來為 \(\log n\) ，這也是使用 \(\text{splay}\) 的一個主要原因。
代碼很短：
void access(int k) {
int son = 0;
while(k) {
splay(k);
s[k].ch[1] = son; pushup(k);
son = k; k = s[k].fa;
}
}
\(\text{LCT}\) 中的 \(\text{findrt}\) 操作
查找 \(x\) 所在的連通塊的根，先 \(\text{access(x)}\) ，根節點一定是當前 \(\text{splay}\) 中最小的結點，一直向左即可，最後 \(\text{splay}\) 一下根節點。
int findrt(int k) {
access(k); splay(k);
while(s[k].ch[0]) pushdown(k), k = s[k].ch[0];
splay(k); return k;
}
這個操作後找到的根，成為了他所在連通塊的根。
\(\text{LCT}\) 中的 \(\text{makeroot}\) 操作
將 \(x\) 點設為所在連通塊的根。
首先打通 \(x\) 與根節點的路徑，此時 \(x\) 為 \(\text{splay}\) 中深度最大的，在最右邊，然後根節點為深度最小的，在最左邊。
本質就是一個區間翻轉了，於是 \(\text{splay}\) 加個 \(\text{tag}\) 維護一下就好了。
void pushdown(int k) {
if(s[k].tag) {
swap(s[k].ch[0], s[k].ch[1]);
if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
s[k].tag = 0;
}
}
void pushall(int k) {
if(chk(k) != -1) pushall(s[k].fa);
pushdown(k);
}
然後這樣在 \(\text{splay}\) 操作開頭需要添加一行 \(\text{pushall(k)}\) 。
\(\text{LCT}\) 中的 \(\text{spilt(x, y)}\) 操作
將 \(x\) 和 \(y\) 之間的路徑拉成一條實鏈。
那簡單，將 \(x\) 設為所在連通塊根之後，與 \(y\) 拉出一條路徑就好了。
void spilt(int x,int y) { makeroot(x); access(y); splay(y); }
在經過這個操作之後, \(y\) 成為了 \(x\) 的父親，\(x\) 為 \(y\) 的左兒子。
\(\text{LCT}\) 中的 \(\text{link(x, y)}\) 操作
這就是加邊操作了，感覺好簡單。
先將 \(x\) 變成所在連通塊根，然後直接看 \(y\) 在不在這個連通塊，沒有直接將 \(x\) 父親設為 \(y\) 就好了。
void link(int x,int y) {
makeroot(x);
if(findrt(y) == x) return;
s[x].fa = y;
}
\(\text{LCT}\) 中的 \(\text{cut(x, y)}\) 操作
刪邊操作，寫鍋了好幾次，最後還是看了別人的/ll
首先將 \(x\) 設為根，然後判斷 \(x, y\) 在不在同一個連通塊，不在證明不存在這個邊。
然後，由於判斷在同一連通塊的時候，採用的是 findrt(y) == x 這個時候執行了 \(\text{findrt(y)}\) 於是，此時 \(x\) 仍然為連通塊根節點，然後 \(x\) 為他的左兒子。
然後當 \(y\) 為 \(\text{splay}\) 中 \(x\) 的下一位才會有邊，於是判斷一下，殺完了。
bool cut(int x,int y) {
makeroot(x);
if(findrt(y) != x || s[y].ch[0] || s[y].fa != x) return 0;
s[y].fa = s[x].ch[1] = 0;
pushup(x);
return 1;
}
放上洛谷模板題目代碼：
// 德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛德麗莎你好可愛
// 德麗莎的可愛在於德麗莎很可愛，德麗莎為什麼很可愛呢，這是因為德麗莎很可愛！
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6;
int n, m, a[N];
struct node {
int ch[2], fa, val, sum, tag;
} s[N];
void pushup(int k) {
s[k].sum = s[ s[k].ch[0] ].sum ^ s[ s[k].ch[1] ].sum ^ s[k].val;
}
void pushdown(int k) {
if(s[k].tag) {
swap(s[k].ch[0], s[k].ch[1]);
if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
s[k].tag = 0;
}
}
int chk(int k) {
if(s[ s[k].fa ].ch[1] == k) return 1;
if(s[ s[k].fa ].ch[0] == k) return 0;
return -1;
}
void pushall(int k) {
if(chk(k) != -1) pushall(s[k].fa);
pushdown(k);
}
void connect(int k,int fa,int op) {
s[k].fa = fa;
if(op == 1) s[fa].ch[1] = k;
if(op == 0) s[fa].ch[0] = k;
}
void rotate(int x) {
int y = s[x].fa, z = s[y]. fa;
int sx = chk(x), sy = chk(y), u = 0;
if(sx == 1) u = s[x].ch[0];
if(sx == 0) u = s[x].ch[1];
connect(u, y, sx); connect(y, x, sx ^ 1); connect(x, z, sy);
pushup(y); pushup(x);
}
void splay(int k) {
pushall(k);
while(chk(k) != -1) {
int y = s[k].fa;
if(chk(y) == -1) rotate(k);
else if(chk(k) == chk(y)) rotate(y), rotate(k);
else rotate(k), rotate(k);
}
}
void access(int k) {
int son = 0;
while(k) {
splay(k);
s[k].ch[1] = son; pushup(k);
son = k; k = s[k].fa;
}
}
void makeroot(int k) {
access(k); splay(k);
swap(s[k].ch[0], s[k].ch[1]);
if(s[k].ch[0]) s[s[k].ch[0]].tag ^= 1;
if(s[k].ch[1]) s[s[k].ch[1]].tag ^= 1;
}
void spilt(int x,int y) {
makeroot(x); access(y); splay(y);
}
int findrt(int k) {
access(k); splay(k);
while(s[k].ch[0]) pushdown(k), k = s[k].ch[0];
splay(k); return k;
}
void link(int x,int y) {
makeroot(x);
if(findrt(y) == x) return;
s[x].fa = y;
}
bool cut(int x,int y) {
makeroot(x);
if(findrt(y) != x || s[y].ch[0] || s[y].fa != x) return 0;
s[y].fa = s[x].ch[1] = 0;
pushup(x);
return 1;
}
signed main () {
ios :: sync_with_stdio( 0 );
cin.tie( 0 ), cout.tie( 0 );
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> s[i].val, s[i].sum = s[i].val;
for(int i = 1; i <= m; i++) {
int op, x, y; cin >> op >> x >> y;
if(op == 0) spilt(x, y), cout << s[y].sum << "\n";
if(op == 1) link(x, y);
if(op == 2) cut(x, y);
if(op == 3) splay(x), s[x].val = y;
}
return 0;
}
未完待續， lct 很好玩的/mgx
