P3224 永无乡

发表于 分类于 阅读次数： Waline： 本文字数： 517 阅读时长 ≈ 2 分钟

考点

  • 并查集
  • 线段树合并

题解

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 50;
int n, m, a[maxn], fa[maxn], root[maxn];
// 动态开点权值线段树，保存不同重要度的个数
// lc：左孩子
// rc：右孩子
// s：区间个数和
// id：只会保存在叶子节点，相同排名保存一个就行了
int tot, lc[30 * maxn], rc[30 * maxn], s[30 * maxn], id[30 * maxn];

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

int build(int p, int l, int r, int i, int v) {
  if (!p) p = ++tot;
  if (l == r) {
    s[p]++;
    id[p] = i;
    return p;
  }
  int mid = (l + r) >> 1;
  if (v <= mid) lc[p] = build(lc[p], l, mid, i, v);
  if (v > mid) rc[p] = build(rc[p], mid + 1, r, i, v);
  s[p] = s[lc[p]] + s[rc[p]];
  return p;
}

int merge(int p, int q, int l, int r) {
  if (!p) return q;
  if (!q) return p;
  if (l == r) {
    s[p] += s[q];
    return p;
  }
  int mid = (l + r) >> 1;
  lc[p] = merge(lc[p], lc[q], l, mid);
  rc[p] = merge(rc[p], rc[q], mid + 1, r);
  s[p] = s[lc[p]] + s[rc[p]];
  return p;
}

int ask(int p, int l, int r, int v) {
  if (l == r) return id[p];
  int mid = (l + r) >> 1, ans = -1;
  if (lc[p] && v <= s[lc[p]])
    ans = ask(lc[p], l, mid, v);
  else if (rc[p])
    ans = ask(rc[p], mid + 1, r, v - s[lc[p]]);
  return ans;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int x, y;
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    fa[i] = i;
    // 每个点都开一个线段树
    root[i] = build(root[i], 1, n, i, a[i]);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> x >> y;
    x = find(x), y = find(y);
    if (x == y) continue;
    fa[y] = x;
    root[x] = merge(root[x], root[y], 1, n);
  }
  cin >> m;
  char c;
  while (m--) {
    cin >> c >> x >> y;
    if (c == 'Q') {
      x = find(x);
      cout << ask(root[x], 1, n, y) << endl;
    } else {
      x = find(x), y = find(y);
      if (x == y) continue;
      fa[y] = x;
      root[x] = merge(root[x], root[y], 1, n);
    }
  }
  return 0;
}

思路

根据题意，每个值的范围仅仅在1 ~ 1e5之间，且同时问你第k大，可以直接使用权值线段树。

每个点都开一个权值线段树，线段树合并时，并到并查集的祖先即可，

这样一来就可以直接检索并查集祖先，来查到该集合的第k大。