DDOSvoid's Blog

CF 1416D Graph and Queries

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/problemset/problem/1416/D

简要题意：给定一个 $n$ 个点 $m$ 条边的简单无向图，点 $i$ 个初始点权为 $w_i$，$w_i$ 构成了一个 $[1,n]$ 的排列，现在有 $q$ 次操作，操作有两种，第一种操作给定 $v$，查询与 $v$ 相连的点中点权最大的点的点权，然后点权最大的这个点的点权置为 $0$；第二种操作给定一个整数 $i$，将第 $i$ 条边删掉

Solution

我们考虑离线按照边被删掉的时间做一个 $kruskal$ 重构树，这样我们每次查询与点 $u$ 相连的点是 $kruskal$ 重构树上的一个点的子树，那么我们现在的操作相当于区间查询和单调修改，使用线段树即可，时间复杂度 $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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 200010
#define Maxn 400010
#define maxm 300010
#define maxq 500010
#define ll long long
using namespace std;

int n, m, q, a[Maxn];

struct Edge {
    int u, v, w;

    friend bool operator < (const Edge &u, const Edge &v) { return u.w < v.w; } 
} e[maxm];

struct Query {
    int opt, x;
} Q[maxq];

struct Kruskal {
    int w, ch[2];
} T[Maxn]; int top;

int fa[Maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); } 

int in[Maxn], out[Maxn], bl[Maxn], f[Maxn][21];
void dfs(int u) {
    static int cnt = 0; 
    in[u] = ++cnt; bl[cnt] = u;
    if (T[u].ch[0]) f[T[u].ch[0]][0] = u, dfs(T[u].ch[0]);
    if (T[u].ch[1]) f[T[u].ch[1]][0] = u, dfs(T[u].ch[1]);
    out[u] = cnt;
}

void init_lca(int n) {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}
int jump(int x, int w) {
    for (int i = 20; ~i; --i)
        if (f[x][i] && T[f[x][i]].w > w) x = f[x][i];
    return x; 
}

namespace Seg {
#define lc i << 1
#define rc i << 1 | 1 
    struct node {
        int v, k;
    } T[Maxn * 4];
    
    inline node maintain(const node &ls, const node &rs) {
        node o;
        o.v = max(ls.v, rs.v);
        if (ls.v > rs.v) o.k = ls.k;
        else o.k = rs.k;
        return o;
    }
    void build(int i, int l, int r) {
        if (l == r) return T[i] = { a[bl[l]], l }, void();
        int m = l + r >> 1;
        build(lc, l, m); build(rc, m + 1, r);
        T[i] = maintain(T[lc], T[rc]);
    }
    void update(int i, int l, int r, int k) {
        if (l == r) return T[i].v = 0, void();
        int m = l + r >> 1;
        if (k <= m) update(lc, l, m, k);
        else update(rc, m + 1, r, k);
        T[i] = maintain(T[lc], T[rc]); 
    }
    node query(int i, int l, int r, int L, int R) {
        if (l > R || r < L) return { 0, 0 };
        if (L <= l && r <= R) return T[i];
        int m = l + r >> 1;
        return maintain(query(lc, l, m, L, R), query(rc, m + 1, r, L, R)); 
    }
} 

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

    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> e[i].u >> e[i].v, e[i].w = q;
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].opt >> Q[i].x;
        if (Q[i].opt == 2) e[Q[i].x].w = i;
    } sort(e + 1, e + m + 1); reverse(e + 1, e + m + 1); init_fa(2 * n - 1); top = n;
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].w, fu, fv;
        if ((fu = find(u)) == (fv = find(v))) continue;
        fa[fu] = fa[fv] = ++top; T[top].ch[0] = fu; T[top].ch[1] = fv; T[top].w = w;
    }
    for (int i = top; i; --i) if (!in[i]) dfs(i);
    init_lca(2 * n - 1); Seg::build(1, 1, top); 
    for (int i = 1, last = 0; i <= q; ++i) {
        int opt = Q[i].opt, x = Q[i].x; if (opt == 2) { last = i; continue; }
        x = jump(x, last); Seg::node t = Seg::query(1, 1, top, in[x], out[x]);
        if (t.k) Seg::update(1, 1, top, t.k);
        cout << t.v << "\n";
    }
    return 0;
}