BZOJ2733【HNOI2012】永无乡 <并查集+线段树合并>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

【HNOI2012】永无乡

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  128  MB\mathrm{Memory\;Limit:\;128\;MB}

Description

永无乡包含nn座岛，编号从11到nn，每座岛都有自己的独一无二的重要度，按照重要度可以将这nn座岛排名，名次用11到nn来表示。
某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛aa出发经过若干座（含00座）桥可以到达岛bb，则称岛aa和岛bb是连通的。
现在有两种操作：
B  x  y\mathrm{B}\;x\;y：表示在岛xx与岛yy之间修建一座新桥。
Q  x  k\mathrm{Q}\;x\;k：表示询问当前与岛xx连通的所有岛中第kk重要的是哪座岛，即所有与岛xx连通的岛中重要度排名第kk小的岛是哪座，请你输出那个岛的编号。

Input

第一行是用空格隔开的两个正整数nn和mm，分别表示岛的个数以及一开始存在的桥数。
接下来的一行是用空格隔开的nn个数，依次描述从岛11到岛nn的重要度排名。
随后的mm行每行是用空格隔开的两个正整数aia_i和bib_i，表示一开始就存在一座连接岛aia_i和岛bib_i的桥。
后面剩下的部分描述操作。
该部分的第一行是一个正整数qq，表示一共有qq个操作。
接下来的qq行依次描述每个操作，操作的格式如上所述，以大写字母Q\mathrm{Q}或B\mathrm{B}开始，后面跟两个不超过nn的正整数，字母与数字以及两个数字之间用空格隔开。

Output

对于每个Q\mathrm{Q}操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。
如果该岛屿不存在，则输出−1-1。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

Sample Output

1
2
3
4
5
-1
2
5
1
2

HINT

对于20%20\%的数据，n≤103,q≤103n\le10^3,q\le10^3
对于100%100\%的数据，n≤105,  m≤n,q≤3×105n\le10^5,\;m≤n,q\le3\times10^5

标签：并查集 线段树合并

Solution

线段树合并裸题。

只建桥不拆桥，可以用并查集维护是否在同一连通块内，在每个连通块内维护一棵值域线段树，这样可以查第kk小。对于建桥的操作，用并查集找出是那两个块合并到一起，将两个块内的线段树合并起来。

线段树合并只需要用函数式线段树动态开点，并像可并堆那样递归合并即可。

Code

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
#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], b[MAX_N+5];
int sz, rt[MAX_N+5], fa[MAX_N+5];
struct node {int ls, rs, val;} tr[MAX_N*20];
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void modify(int &v, int s, int t, int p) {
    if (!v) v = ++sz;
    if (s == t) {tr[v].val++; return;}
    if (p <= mid) modify(tr[v].ls, s, mid, p);
    if (p >= mid+1) modify(tr[v].rs, mid+1, t, p);
    tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;
}
int query(int v, int s, int t, int k) {
    if (s == t) return s; int lsz = tr[tr[v].ls].val;
    if (lsz >= k) return query(tr[v].ls, s, mid, k);
    return query(tr[v].rs, mid+1, t, k-lsz);
}
int merge(int x, int y) {
    if (!x) return y; if (!y) return x;
    tr[x].ls = merge(tr[x].ls, tr[y].ls);
    tr[x].rs = merge(tr[x].rs, tr[y].rs);
    tr[x].val = tr[tr[x].ls].val+tr[tr[x].rs].val;
    return x;
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]), b[a[i]] = i, fa[i] = i;
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), u = getf(u), v = getf(v), fa[v] = u;
    for (int i = 1; i <= n; i++) modify(rt[getf(i)], 1, n, a[i]);
    int T; read(T);
    while (T--) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'B') {
            int x, y; read(x), read(y), x = getf(x), y = getf(y);
            if (x^y) fa[y] = x, rt[x] = merge(rt[x], rt[y]);
        } else {
            int x, k; read(x), read(k);
            if (tr[rt[x = getf(x)]].val < k) puts("-1");
            else printf("%d\n", b[query(rt[x], 1, n, k)]);
        }
    }
    return 0;
}