题目链接:http://poj.org/problem?id=2985 并查集合并小组,这个自然是不用说的,主要的问题是怎么求第K大值。 首先,线段树每一个结点存储的是组内元素的个数区间内有多少个组,初始化的时候所有的组中都是一个元素,所以当区间左端点为1的时候,结点的值为n,然后每次合并,原有小组的空间内结点值-1,合并后的新组空间内结点值+1,线段树这么维护完了以后,询问过程中,如果右子树的值大于k,那么第k大数一定在右子树当中。
![](/Images/OutliningIndicators/ContractedBlock.gif) 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
|