题目描述
blablabla
样例
blablabla
算法1
(可持续化平衡树) 时间$O(n \times logn)$ 空间$O(n)$
首先你要会可持续化平衡树, 不会先去学FHQ
然后这题就变成了和普通的可持续化数据结构
$rt_i$表示以$i$为根的平衡树, 合并的时候后按随即权重合并就行了
合并期望复杂度$O(logn)$
时间复杂度 $O(n \times logn)$
参考文献
C++ 代码
struct FHQ {
FHQ() { srand(time(0)); }
struct Node {
int ch[2], val, pri; ll siz;
int& operator [](int k) { return ch[k]; }
} tr[N];
int rt[N], tot;
void push_up(int p) { tr[p].siz = tr[tr[p][0]].siz + tr[tr[p][1]].siz + 1; }
int newNode(int v) {
tr[++tot].val = v; tr[tot].siz = 1;
return tr[tot].pri = rand(), tot;
}
void split_v(int p, int k, int& x, int& y) {
if (!p) x = y = 0;
else {
if (tr[p].val <= k) x = p, split_v(tr[p][1], k, tr[p][1], y);
else y = p, split_v(tr[p][0], k, x, tr[p][0]);
push_up(p);
}
}
void split_k(int p, int k, int& x, int& y) {
if (!p) x = y = 0;
else {
if (tr[tr[p][0]].siz + 1 <= k) x = p, split_k(tr[p][1], k, tr[p][1], y);
else y = p, split_k(tr[p][0], k, x, tr[p][0]);
push_up(p);
}
}
int merge(int x, int y) {
if (!x || !y) return x | y;
if (tr[x].pri < tr[y].pri) tr[x][1] = merge(tr[x][1], y);
else tr[y][0] = merge(x, tr[y][0]), swap(x, y);
push_up(x); return x;
}
int unit(int x, int y) {
if (!x || !y) return x | y;
if (tr[x].pri > tr[y].pri) swap(x, y);
int a, b, c; split_v(y, tr[x].val, a, b); split_v(a, tr[x].val - 1, a, c);
tr[x][0] = unit(tr[x][0], a); tr[x][1] = unit(tr[x][1], b);
push_up(x); return x;
}
int kth(int p, ll k) {
if (k > tr[p].siz) return 0;
while (1)
if (tr[tr[p][0]].siz >= k) p = tr[p][0];
else if (tr[tr[p][0]].siz + 1 == k) return tr[p].val;
else k -= tr[tr[p][0]].siz + 1, p = tr[p][1];
}
} T;
int n, m, _, k, cas;
int rk[N], f[N];
int ff(int x) { return x == f[x] ? x : f[x] = ff(f[x]); }
int main() {
IOS; cin >> n >> m; rk[0] = -1;
rep(i, 1, n) {
int val; cin >> val; rk[val] = i;
T.rt[i] = T.newNode(val); f[i] = i;
}
rep(i, 1, m) {
int u, v; cin >> u >> v;
if ((u = ff(u)) > (v = ff(v))) swap(u, v);
T.rt[u] = T.unit(T.rt[u], T.rt[v]); f[v] = u;
}
for (cin >> _; _; --_) {
char op; int u, v; cin >> op >> u >> v;
if (op == 'Q') cout << rk[T.kth(T.rt[ff(u)], v)] << '\n';
else {
if ((u = ff(u)) > (v = ff(v))) swap(u, v);
T.rt[u] = T.unit(T.rt[u], T.rt[v]); f[v] = u;
}
}
return 0;
}