題面

沒有權限號的可以去LOJ

Sol

大家都知道，\(LCT\)上有許多實邊和虛邊
實邊就是每棵\(Splay\)上的既認父親又認兒子的邊
虛邊就是\(Splay\)和\(Splay\)之間只認父親的的邊
那么每個點就有它的虛兒子和實兒子，實際上虛兒子才是它在\(LCT\)維護的樹上的真正的兒子
當你\(Access(x)\)時，\(x\)的虛兒子加上它自己就是它子樹的信息
所以我們要維護每個點虛兒子的信息和LCT子樹的信息（也就是虛兒子+實兒子+自己）
怎么維護？
你會發現這只會在\(Access\)和\(Link\)操作中改變
\(Access\)時，這個點的實兒子和虛兒子會有改變，那么維護的虛兒子的信息就減去原來的加上現在的就好了
\(Link\)時，這個點多了一個虛兒子，直接加上就好，但是這個點的祖先都要更改，不好操作，直接把它也\(Makeroot\)就好
LCT子樹的信息可以直接寫在\(Update\)內

然后這個題就是水題了

詢問就是兩邊\(size\)的乘積

# include <bits/stdc++.h> # define IL inline # define RG register # define ls ch[0][x] # define rs ch[1][x] # define Fill(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; const int _(1e5 + 10);IL ll Read(){RG char c = getchar(); RG ll x = 0, z = 1;for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);return x * z; }int n, Q, ch[2][_], fa[_], size[_], sum[_], rev[_], S[_];IL bool Son(RG int x){ return ch[1][fa[x]] == x; }IL bool Isroot(RG int x){ return ch[0][fa[x]] != x && ch[1][fa[x]] != x; }IL void Reverse(RG int x){ if(!x) return; swap(ls, rs); rev[x] ^= 1; }IL void Update(RG int x){ sum[x] = sum[ls] + sum[rs] + size[x] + 1; }IL void Pushdown(RG int x){ if(!rev[x]) return; Reverse(ls); Reverse(rs); rev[x] = 0; }IL void Rotate(RG int x){RG int y = fa[x], z = fa[y], c = Son(x);if(!Isroot(y)) ch[Son(y)][z] = x; fa[x] = z;ch[c][y] = ch[!c][x]; fa[ch[c][y]] = y;ch[!c][x] = y; fa[y] = x; Update(y); }IL void Splay(RG int x){S[S[0] = 1] = x;for(RG int y = x; !Isroot(y); y = fa[y]) S[++S[0]] = fa[y];while(S[0]) Pushdown(S[S[0]--]);for(RG int y = fa[x]; !Isroot(x); Rotate(x), y = fa[x])if(!Isroot(y)) Son(x) ^ Son(y) ? Rotate(x) : Rotate(y);Update(x); }IL void Access(RG int x){for(RG int y = 0; x; y = x, x = fa[x]) Splay(x), size[x] += sum[ch[1][x]] - sum[y], ch[1][x] = y, Update(x); }IL void Makeroot(RG int x){ Access(x); Splay(x); Reverse(x); }IL void Link(RG int x, RG int y){ Makeroot(x); Makeroot(y); fa[x] = y; size[y] += sum[x]; Update(y); }IL void Split(RG int x, RG int y){ Makeroot(x); Access(y); Splay(y); }int main(RG int argc, RG char* argv[]){n = Read(); Q = Read();while(Q--){RG char op; scanf(" %c", &op); RG int x = Read(), y = Read();if(op == 'A') Link(x, y);else Split(x, y), printf("%lld\n", 1LL * sum[x] * (sum[y] - sum[x]));}return 0; }

轉載于:https://www.cnblogs.com/cjoieryl/p/8329269.html

總結

以上是生活随笔為你收集整理的LCT维护子树信息(BZOJ4530：[BJOI2014]大融合)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。