[BZOJ 2733][HNOI 2012] 永无乡

题目大意

\(n\) 座岛屿,给出每座岛屿的重要度排名(不会并列),同时有 \(m\) 条边连接这些岛屿。现有 \(q\) 次操作,操作有两种:

  • B x y:在岛屿 \(x\)\(y\) 之间连一条边。
  • Q x k:查询与岛屿 \(x\) 连通的所有岛屿中,重要度第 \(k\) 大(排名第 \(k\) 小)的岛屿。

\(1 \leqslant n, \; m \leqslant 100,000\)

\(1 \leqslant q \leqslant 300,000\)

题目链接

BZOJ 2733

CodeVS 1477

题解

并查集维护连通性,权值线段树维护区间信息。

连接两个点时,并查集合并对应的点,两个线段树也合并。查询时在对应线段树中查询。

想着这么多棵线段树,于是用了动态开点。。。

另外这个线段树合并并不算是完全的线段树合并,因为同一个权值不会有第二个。。。所以不太能作线段树合并的版子。。。

代码

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
#include <cstdio>
const int MAXN = 100005;
struct SegT {
struct Node {
Node *lc, *rc;
int l, r, cnt, sum;
Node(int l, int r, Node *lc = NULL, Node *rc = NULL) : l(l), r(r), lc(lc), rc(rc), cnt(0), sum(0) {}
void maintain() {
sum = (lc ? lc->sum : 0) + (rc ? rc->sum : 0);
}
void pushDown() {
if (lc && rc) return;
int mid = l + (r - l) / 2;
if (!lc) lc = new Node(l, mid);
if (!rc) rc = new Node(mid + 1, r);
}
void insert(int val) {
if (l == r) {
cnt = sum = 1;
return;
}
pushDown();
int mid = l + (r - l) / 2;
if (val <= mid) lc->insert(val);
else rc->insert(val);
maintain();
}
} *root;
SegT() : root(NULL) {}
int query(int k) {
Node *u = root;
if (u->sum < k) return -1;
while (u->l != u->r) {
u->pushDown();
if (u->lc->sum >= k) u = u->lc;
else k -= u->lc->sum, u = u->rc;
}
return u->l;
}
void insert(int val) {
root->insert(val);
}
void init(int l, int r) {
root = new Node(l, r);
}
} segT[MAXN];
SegT::Node *merge(SegT::Node *a, SegT::Node *b) {
if (!a->sum) return b;
if (!b->sum) return a;
a->lc = merge(a->lc, b->lc);
a->rc = merge(a->rc, b->rc);
a->maintain();
return a;
}
struct UnionFindSet {
int fa[MAXN];
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
int p = find(x), q = find(y);
if (p == q) return;
fa[q] = p;
}
void init(int n) {
for (int i = 1; i <= n; i++) fa[i] = i;
}
} ufs;
int main() {
int n, m;
scanf("%d %d", &n, &m);
static int w[MAXN], id[MAXN];
for (int i = 1; i <= n; i++) {
scanf("%d", &w[i]);
id[w[i]] = i;
}
ufs.init(n);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
ufs.merge(u, v);
}
for (int i = 1; i <= n; i++) segT[i].init(1, n);
for (int i = 1; i <= n; i++) segT[ufs.find(i)].insert(w[i]);
int q;
scanf("%d", &q);
while (q--) {
char op[2];
int x, y;
scanf("%s %d %d", op, &x, &y);
if (op[0] == 'Q') {
int temp = segT[ufs.find(x)].query(y);
printf("%d\n", temp == -1 ? temp : id[temp]);
}
else {
int p = ufs.find(x), q = ufs.find(y);
if (p != q) {
ufs.fa[q] = p;
segT[p].root = merge(segT[p].root, segT[q].root);
}
}
}
return 0;
}