题解 P3224 【[HNOI2012]永无乡】
Ireliaღ
2019-05-29 12:02:24
_这么好的一道平衡树题，怎么没人写替罪羊啊，明明是最好写的平衡树_
## 本题第一篇替罪羊树题解
思路挺好想，用$n$个平衡树和并查集，维护每个联通块内各个岛屿的优先级。注意二叉排序树中节点的优先级。
合并时，直接把节点少的平衡树里面每个节点暴力塞到节点多的平衡树中，均摊复杂度是对的。
### 代码
替罪羊树+启发式合并
```cpp
// luogu-judger-enable-o2
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> poi;
const float Alpha = 0.7;
const int MAXN = 1e5 + 5;
int n, m;
class SGTree{
private :
struct Node{
poi val;
int cnt;
int siz, cov;
Node *ch[2];
Node(poi val) : val(val) {
cnt = true;
siz = 1;
cov = 1;
ch[0] = NULL;
ch[1] = NULL;
}
void Update() {
siz = cnt + (ch[0] ? ch[0]->siz : 0) + (ch[1] ? ch[1]->siz : 0);
cov = 1 + (ch[0] ? ch[0]->cov : 0) + (ch[1] ? ch[1]->cov : 0);
}
bool Bad() {
int ls = (ch[0] ? ch[0]->cov : 0), rs = (ch[1] ? ch[1]->cov : 0);
return (float)ls > (float)cov * Alpha || (float)rs > (float)cov * Alpha;
}
};
Node *rt;
vector<Node*> vec;
void Dfs(Node *now) {
if (!now) return;
Dfs(now->ch[0]);
if (now->cnt) vec.push_back(now);
Dfs(now->ch[1]);
now->ch[0] = now->ch[1] = NULL;
now->Update();
}
void Rebuild(Node *&now, int l, int r) {
if (l > r) return;
int mid = l + r >> 1;
now = vec[mid];
Rebuild(now->ch[0], l, mid - 1);
Rebuild(now->ch[1], mid + 1, r);
now->Update();
}
void Insert(Node *&now, poi k) {
if (!now) {
now = new Node(k);
return;
}
if (k < now->val) Insert(now->ch[0], k);
else if (k == now->val) now->cnt++;
else Insert(now->ch[1], k);
now->Update();
if (now->Bad()) {
vec.clear();
Dfs(now);
int sz = vec.size();
Rebuild(now, 0, sz - 1);
}
}
void Remove(Node *now, poi k) {
if (!now) return;
if (k < now->val) {
Remove(now->ch[0], k);
} else if (k == now->val) {
if (now->cnt) now->cnt--;
} else {
Remove(now->ch[1], k);
}
now->Update();
}
poi Kth(Node *now, int k) {
if (!now) return make_pair(0, 0);
int ls = (now->ch[0] ? now->ch[0]->siz : 0);
if (k <= ls) return Kth(now->ch[0], k);
else if (k == ls + 1) return now->val;
else return Kth(now->ch[1], k - now->cnt - ls);
}
void PopInto(SGTree &tree, Node *now) {
if (!now) return;
for (int i = 1; i <= now->cnt; i++) tree.Insert(now->val);
PopInto(tree, now->ch[0]);
PopInto(tree, now->ch[1]);
delete now;
}
public :
SGTree() {
rt = NULL;
vec.clear();
}
void Insert(poi k) {
Insert(rt, k);
}
void Join(SGTree &tree) {
tree.PopInto(*this, tree.rt);
}
poi Kth(int k) {
return Kth(rt, k);
}
int Size() {
return rt ? rt->siz : 0;
}
};
SGTree tr[MAXN];
int bel[MAXN];
int Find(int x) {
if (bel[x] == x) return x;
return bel[x] = Find(bel[x]);
}
void Build(int a, int b) {
int u = Find(a), v = Find(b);
if (tr[u].Size() > tr[v].Size()) swap(u, v);
bel[u] = v;
tr[v].Join(tr[u]);
}
int main() {
cin >> n >> m;
int x, y, k, u, v;
char op[5];
for (int i = 1; i <= n; i++) bel[i] = i;
for (int i = 1; i <= n; i++) {
cin >> k;
tr[i].Insert(make_pair(k, i));
}
for (int i = 1; i <= m; i++) {
cin >> x >> y;
Build(x, y);
}
int q;
cin >> q;
for (int i = 1; i <= q; i++) {
cin >> op;
if (op[0] == 'Q') {
cin >> x >> k;
u = Find(x);
if (tr[u].Size() < k) {
cout << -1 << endl;
continue;
}
cout << tr[u].Kth(k).second << endl;
} else {
cin >> x >> y;
Build(x, y);
}
}
return 0;
}
```