DDOSvoid's Blog

Luogu P4219 [BJOI2014]大融合

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4219

简要题意：给定 $n$ 个点，现在有 $m$ 个操作，操作有两种，第一种操作是给定 $x,y$，加入一条 $(x,y)$ 的无向边，保证任意时刻都为森林；第二种操作是给定 $x,y$，保证 $(x,y)$ 这条边存在，求有多少对点的最短路径经过这条边

Solution

容易发现操作就是连边同时维护子树 $size$，$\rm LCT$ 可以解决这些问题

时间复杂度 $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <iostream>
#define maxn 100010
using namespace std;

int n, m;

#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct LCT {
    int ch[2], sum, v, val; 
    bool rev;
} T[maxn]; int f[maxn];
inline int get(int i) {
    if (T[f[i]].ch[0] == i) return 0;
    if (T[f[i]].ch[1] == i) return 1;
    return -1;
}

inline void maintain(int i) { T[i].sum = T[i].val + T[lc].sum + T[rc].sum + T[i].v; }

inline void setr(int i) {
    if (!i) return ;
    T[i].rev ^= 1; swap(lc, rc); 
}

inline void push(int i) {
    bool &rev = T[i].rev; if (!rev) return ;
    setr(lc); setr(rc);
    rev = 0;
}

inline void rotate(int x) {
    int fa = f[x], ffa = f[f[x]], wx = get(x);
    if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
    f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
    T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
    maintain(fa); maintain(x); 
} 

void clt(int i) {
    static int st[maxn], top;
    st[top = 1] = i;
    while (~get(i)) st[++top] = i = f[i];
    while (top) push(st[top--]);
}

void Splay(int i) {
    clt(i);
    for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
        if (~get(fa)) rotate(get(fa) == get(i) ? fa : i);
}

void access(int i) {
    for (int p = 0; i; i = f[p = i]) {
        Splay(i);
        if (rc) T[i].v += T[rc].sum;
        if (p) T[i].v -= T[p].sum;
        rc = p; maintain(i);
    }
}

inline void make_rt(int i) { access(i); Splay(i); setr(i); }

inline void split(int x, int y) { make_rt(x); access(y); Splay(y); }

inline void link(int x, int y) {
    split(x, y); f[x] = y;
    T[y].v += T[x].sum; maintain(y);
}

inline void solve_1() {
    int x, y; cin >> x >> y;
    link(x, y); 
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    split(x, y);
    cout << 1ll * (T[x].v + T[x].val) * (T[y].v + T[y].val) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) T[i].val = 1;
    for (int i = 1; i <= m; ++i) {
        char s[10]; cin >> s;
        switch (s[0]) {
        case 'A': solve_1(); break;
        case 'Q': solve_2(); break;
        }
    }
    return 0;
}