题目链接:https://www.luogu.com.cn/problem/P3224
主要知识点是:树上启发式合并,即每次合并将小的树里面的每个点合并大大的树里面,时间复杂度 \(O(n \log^2 n)\)。
同时需要开并查集维护集合关系。
示例程序:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;
struct Node {
int s[2], p, v, id, sz;
Node() {}
Node(int _v, int _id, int _p) {
v = _v; id = _id; p = _p;
sz = 1;
s[0] = s[1] = 0;
}
} tr[maxn];
int root[maxn], idx;
int p[maxn];
int find(int x) {
return x == p[x] ? x : p[x] = find(p[x]);
}
void push_up(int x) {
tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1;
}
void f_s(int p, int u, bool k) {
tr[p].s[k] = u;
tr[u].p = p;
}
void rot(int x) {
int y = tr[x].p, z = tr[y].p;
bool k = tr[y].s[1] == x;
f_s(z, x, tr[z].s[1]==y);
f_s(y, tr[x].s[k^1], k);
f_s(x, y, k^1);
push_up(y), push_up(x);
}
void splay(int x, int k, int b) {
while (tr[x].p != k) {
int y = tr[x].p, z = tr[y].p;
if (z != k)
(tr[y].s[1]==x) ^ (tr[z].s[1]==y) ? rot(x) : rot(y);
rot(x);
}
if (!k) root[b] = x;
}
void ins(int v, int id, int b) {
int u = root[b], p = 0;
while (u) p = u, u = tr[u].s[v > tr[u].v];
tr[u = ++idx] = Node(v, id, p);
if (p) tr[p].s[v > tr[p].v] = u;
splay(u, 0, b);
}
int get_k(int k, int b) {
int u = root[b];
while (u) {
if (tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
else if (tr[tr[u].s[0]].sz + 1 == k) return tr[u].id;
else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
}
return -1;
}
void dfs(int u, int b) {
if (tr[u].s[0]) dfs(tr[u].s[0], b);
if (tr[u].s[1]) dfs(tr[u].s[1], b);
ins(tr[u].v, tr[u].id, b);
}
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
p[i] = root[i] = i;
int v;
scanf("%d", &v);
tr[i] = Node(v, i, 0);
}
idx = n;
while (m--) {
int a, b;
scanf("%d%d", &a, &b);
a = find(a), b = find(b);
if (a != b) {
if (tr[root[a]].sz > tr[root[b]].sz) swap(a, b);
dfs(root[a], b);
p[a] = b;
}
}
scanf("%d", &m);
while (m--) {
char op[2];
int a, b;
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'B') {
a = find(a), b = find(b);
if (a != b) {
if (tr[root[a]].sz > tr[root[b]].sz) swap(a, b);
dfs(root[a], b);
p[a] = b;
}
}
else {
a = find(a);
if (tr[root[a]].sz < b) puts("-1");
else printf("%d\n", get_k(b, a));
}
}
return 0;
}
标签:sz,洛谷,int,题解,void,tree,tr,root,id
From: https://www.cnblogs.com/quanjun/p/16988959.html