题意
给定 \(n\) 个集合,每个集合最开始只包含数 \(a_i\),然后进行 \(m\) 次合并操作。具体地,每次操作将数 \(a_i\) 所在的集合与数 \(a_j\) 所在的集合合并。
接下来,进行 \(q\) 次操作,每次操作可能为合并操作与查询操作,合并操作与上述相同,查询操作为查询数 \(a_x\) 所在的集合中第 \(k\) 小的数的下标。
sol
这里的查询操作为根据排名查数,且需要维护集合的合并操作,因此使用并查集套平衡树。平衡树使用 FHQ-Treap,具体用法见[lnsyoj285/luoguP2596/ZJOI2006]书架。
需要注意的是,虽然使用的是以分裂与合并为基本操作的 FHQ-Treap,但不能直接使用 FHQ-Treap 的合并操作来进行平衡树的合并。因为 FHQ-Treap 所合并的两棵平衡树必须内部节点的值域没有交集(按值分裂)或在序列中的位置没有交集(按排名分裂)。我们只能使用启发式合并。
启发式合并
平衡树的启发式合并非常简单,只需要将较小的那棵树的每一个节点都插入另一棵树中即可,可以递归进行处理。
代码(此处假设被插入树的元素个数大于插入树的元素个数):
void merge_tree(int &r, int u){ // r 为被插入树的根,u 为应插入的节点编号
if (tr[u].l) merge_tree(r, tr[u].l);
if (tr[u].r) merge_tree(r, tr[u].r);
tr[u].l = tr[u].r = 0;
insert(r, u);
}
查询操作为 BST(二叉搜索树)的基本操作,具体移步[lnsyoj118/luoguP3369]普通平衡树
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 100005;
struct Node{
int l, r;
int key, val;
int size;
}tr[N];
int fa[N];
int n, m, q;
int idx;
int root[N];
int find(int x){
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
int create(int key){
tr[ ++ idx].key = key;
tr[idx].val = rand();
tr[idx].size = 1;
return idx;
}
void pushup(int u){
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}
void split(int u, int key, int &x, int &y){
if (!u) {
x = y = 0;
return ;
}
if (tr[u].key <= key) x = u, split(tr[u].r, key, tr[x].r, y);
else y = u, split(tr[u].l, key, x, tr[y].l);
pushup(u);
}
int merge(int x, int y){
if (!x || !y) return x | y;
if (tr[x].val <= tr[y].val){
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
}
else {
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
void insert(int &r, int u){
int r1 = 0, r2 = 0;
split(r, tr[u].key, r1, r2);
r = merge(r1, merge(u, r2));
}
void merge_tree(int &r, int u){
if (tr[u].l) merge_tree(r, tr[u].l);
if (tr[u].r) merge_tree(r, tr[u].r);
tr[u].l = tr[u].r = 0;
insert(r, u);
}
int get_key(int u, int rank){
if (rank > tr[u].size) return -1;
if (tr[tr[u].l].size >= rank) return get_key(tr[u].l, rank);
if (tr[tr[u].l].size + 1 == rank) return u;
return get_key(tr[u].r, rank - tr[tr[u].l].size - 1);
}
int main(){
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ){
int t;
scanf("%d", &t);
root[i] = create(t);
fa[i] = i;
}
while (m -- ){
int x, y;
scanf("%d%d", &x, &y);
int fx = find(x), fy = find(y);
if (fx == fy) continue;
if (tr[root[fx]].size < tr[root[fy]].size) swap(fx, fy);
fa[fy] = fx;
merge_tree(root[fx], root[fy]);
}
scanf("%d", &q);
while (q -- ){
char op[2];
int x, y;
scanf("%s%d%d", op, &x, &y);
if (*op == 'B'){
int fx = find(x), fy = find(y);
if (fx == fy) continue;
if (tr[root[fx]].size < tr[root[fy]].size) swap(fx, fy);
fa[fy] = fx;
merge_tree(root[fx], root[fy]);
}
else {
int fx = find(x);
int r = root[fx];
printf("%d\n", get_key(r, y));
}
}
}
蒟蒻犯的若至错误
- 使用并查集前没有初始化并查集
- 启发式合并时没有清空插入节点的儿子(不影响其正确性,但会浪费空间)