DDOSvoid's Blog

Luogu P3377 【模板】左偏树（可并堆）

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

题目描述

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

Solution

注意到我们如果直接在左偏树上跳 $fa$ 的复杂度是 $O(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
#include <iostream>
#include <cstdio>
#define maxn 100010
using namespace std;

int n, m; 

#define lc T[x].ch[0]
#define rc T[x].ch[1]
struct Left_Leaning_Tree {
    int v, d, ch[2]; 
} T[maxn]; int fa[maxn];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (T[x].v > T[y].v || (T[x].v == T[y].v && x > y)) swap(x, y);
    rc = merge(rc, y); fa[rc] = x;
    if (T[lc].d < T[rc].d) swap(lc, rc);
    T[x].d = T[rc].d + 1;
    return x; 
} 

bool ext[maxn]; 
void erase(int x) {
    ext[x] = 0; int y = merge(lc, rc);
    fa[x] = fa[y] = y; // 这里不能写 fa[x] = 0, fa[y] = y; 因为在存在路径压缩的情况下，x 的子树内的点可能还没有直接连到 y 上
} 

inline void solve_1() {
    int x, y, fx, fy; cin >> x >> y;
    fx = find(x); fy = find(y);
    if (!ext[x] || !ext[y] || fx == fy) return ;
    merge(fx, fy); 
}

inline void solve_2() {
    int x, fx; cin >> x; fx = find(x); 
    if (!ext[x]) return (void) (cout << "-1\n");
    cout << T[fx].v << "\n"; erase(fx); 
} 

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

    cin >> n >> m; fill(ext, ext + maxn, 1); 
    for (int i = 1; i <= n; ++i) cin >> T[i].v, fa[i] = i; 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    }
    return 0;
}