BZOJ 2733 2733: [HNOI2012]永无乡平衡树启发式合并

2019-11-06 07:49:02

字体：大中小

来源：转载

供稿：网友

Description

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

Input

输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。对于 20%的数据 n≤1000,q≤1000

对于 100%的数据 n≤100000,m≤n，q≤300000

Output

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

Sample Input 5 1

4 3 2 5 1

1 2

Q 3 2

Q 2 1

B 2 3

B 1 5

Q 2 1

Q 2 4

Q 2 3

Sample Output -1

解法：自己手撸的第一个启发式合并的题目了，好像这个启发式合并还挺快的2333。对于合并两个平衡树，我们可以暴力的将size小的平衡树中的所有节点删掉，然后加入大的平衡树中，因为每个点只可能被删除插入logn次，所以时间复杂度为nlog^2n。

//BZOJ 2733 TREAP + DSU//其实没这么长的，我的treap模板比较长2333#include <bits/stdc++.h>using namespace std;const int maxn = 100010;int n, m, fa[maxn], a[maxn], Root[maxn], id[maxn];int find_set(int x){if(x == fa[x]) return x; else return fa[x] = find_set(fa[x]);}namespace multi_treap{ struct data{ int l, r, v, size, rnd, w; }tree[4000005]; int size, root; void update(int k) { tree[k].size = tree[tree[k].l].size + tree[tree[k].r].size + tree[k].w; } void rturn(int &k) { int t = tree[k].l; tree[k].l = tree[t].r; tree[t].r = k; tree[t].size = tree[k].size; update(k); k = t; } void lturn(int &k) { int t = tree[k].r; tree[k].r = tree[t].l; tree[t].l = k; tree[t].size = tree[k].size; update(k); k=t; } void insert(int &k, int x) { if(k == 0) { size++; k = size; tree[k].size = tree[k].w = 1; tree[k].v = x; tree[k].rnd = rand(); return ; } tree[k].size++; if(tree[k].v==x) tree[k].w++;//每个结点顺便记录下与该节点相同值的数的个数 else if(x > tree[k].v) { insert(tree[k].r, x); if(tree[tree[k].r].rnd < tree[k].rnd) lturn(k);//维护堆性质 } else { insert(tree[k].l, x); if(tree[tree[k].l].rnd < tree[k].rnd) rturn(k); } } void del(int &k,int x) { if(k == 0)return; if(tree[k].v == x) { if(tree[k].w > 1) { tree[k].w--; tree[k].size--; return;//若不止相同值的个数有多个，删去一个 } if(tree[k].l * tree[k].r == 0)k = tree[k].l + tree[k].r;//有一个儿子为空 else if(tree[tree[k].l].rnd < tree[tree[k].r].rnd) rturn(k),del(k,x); else lturn(k),del(k,x); } else if(x > tree[k].v) tree[k].size--, del(tree[k].r,x); else tree[k].size--, del(tree[k].l,x); } int query_rank(int k, int x) { if(k == 0) return 0; if(tree[k].v == x) return tree[tree[k].l].size + 1; else if(x > tree[k].v) return tree[tree[k].l].size + tree[k].w + query_rank(tree[k].r, x); else return query_rank(tree[k].l, x); } int query_num(int k, int x) { if(k == 0) return 0; if(x <= tree[tree[k].l].size) return query_num(tree[k].l, x); else if(x > tree[tree[k].l].size + tree[k].w) return query_num(tree[k].r,x - tree[tree[k].l].size-tree[k].w); else return tree[k].v; }}using namespace multi_treap;void combine(int x, int y){ int fx = find_set(x), fy = find_set(y); if(tree[Root[fx]].size < tree[Root[fy]].size) swap(fx, fy); //fx > fy fa[fy] = fx; if(fx == fy) return ; fy = Root[fy]; while(Root[fy]){ insert(Root[fx], a[fy]); del(Root[fy], a[fy]); }}void ask(int x, int k){ x = Root[find_set(x)]; if(tree[x].size >= k) PRintf("%d/n", id[query_num(x, k)]); else puts("-1");}int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) id[a[i]] = i; for(int i = 1; i <= n; i++) fa[i] = i, insert(Root[i], a[i]); while(m--){ int x, y; scanf("%d%d", &x, &y); combine(x, y); } int T; scanf("%d", &T); while(T--){ char s[10]; int x, y; scanf("%s%d%d", s, &x, &y); if(s[0] == 'B') combine(x, y); else ask(x, y); } return 0;}

上一篇：5种控制变量可学习性的方法(PyTorch)

下一篇：[dfs基础]XXX+XXX=XXX