# Irelia

### 题解 P3224 【[HNOI2012]永无乡】

posted on 2019-05-29 12:02:24 | under 题解 |

## 本题第一篇替罪羊树题解

### 代码

// 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);
}

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();
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;
}