题目链接：http://poj.org/problem?id=2985 并查集合并小组，这个自然是不用说的，主要的问题是怎么求第K大值。 首先，线段树每一个结点存储的是组内元素的个数区间内有多少个组，初始化的时候所有的组中都是一个元素，所以当区间左端点为1的时候，结点的值为n，然后每次合并，原有小组的空间内结点值-1，合并后的新组空间内结点值+1，线段树这么维护完了以后，询问过程中，如果右子树的值大于k，那么第k大数一定在右子树当中。
  view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define lson l, m, rt << 1
9 #define rson m + 1, r, rt << 1 | 1
10 const int maxn = 200010;
11 int sum[maxn << 2], n, q;
12 struct data{
13 int p, num;
14 }p[maxn];
15 void build(int l, int r, int rt){
16 if (l == 1) sum[rt] = n;
17 else sum[rt] = 0;
18 if (l == r) return;
19 int m = (l + r) >> 1;
20 build(lson);
21 build(rson);
22 }
23 void update(int x, int f, int l, int r, int rt){
24 if (!f) sum[rt] -= 1;
25 else sum[rt] += 1;
26 if (l == r) return;
27 int m = (l + r) >> 1;
28 if (x <= m) update(x, f, lson);
29 else update(x, f, rson);
30 }
31 void query(int k, int l, int r, int rt){
32 if (l == r){
33 printf("%d\n", l);
34 return;
35 }
36 int m = (l + r) >> 1;
37 if (sum[rt << 1 | 1] >= k) query(k, rson);
38 else query(k - sum[rt << 1 | 1], lson);
39 }
40 int find(int x){
41 if (p[x].p == x) return x;
42 int temp = p[x].p;
43 p[x].p = find(temp);
44 p[x].num = p[temp].num + p[x].num;
45 return p[x].p;
46 }
47 int main(){
48 while (~scanf("%d%d", &n, &q)){
49 for (int i = 0; i <= n; i++){
50 p[i].p = i; p[i].num = 1;
51 }
52 build(1, n, 1);
53 while (q--){
54 int op;
55 scanf("%d", &op);
56 if (op == 0){
57 int x, y;
58 scanf("%d%d", &x, &y);
59 x = find(x);
60 y = find(y);
61 if (x == y) continue;
62 update(p[x].num, 0, 1, n, 1);
63 update(p[y].num, 0, 1, n, 1);
64 update(p[x].num + p[y].num, 1, 1, n, 1);
65 p[y].p = x;
66 p[x].num += p[y].num;
67 }
68 if (op == 1){
69 int k;
70 scanf("%d", &k);
71 query(k, 1, n, 1);
72 }
73 }
74 }
75 return 0;
76 }
77
|