題目連結
題意
給定一個圖,每個點上有權值。兩種操作,連結兩個點;問與某個點連通的所有點中權值為第 k <script type="math/tex" id="MathJax-Element-1">k</script> 小的點的編号。
思路
HDU 3726 Graph and Queries 離線處理 treap + 并查集 的簡易版,直接正着做,也沒有修改操作
Code
#include <bits/stdc++.h>
#define maxn 100010
int fa[maxn], sz[maxn], val[maxn];
using namespace std;
map<int, int> mp;
struct node {
int key, val, sz;
node* ch[];
node() { sz = , key = INT_MAX; }
node(int x);
void update() { sz = ch[]->sz + ch[]->sz + ; }
}*null = new node;
node::node(int x) { val = x, key = rand(), sz = , ch[] = ch[] = null; }
struct Treap {
node* root;
Treap() { root = null; }
void rotate(node*& t, bool d) {
node* p = t->ch[d];
t->ch[d] = p->ch[!d];
p->ch[!d] = t;
t->update(), p->update();
t = p;
}
void insert(node*& t, int x) {
if (t == null) { t = new node(x); return; }
bool dir = x > t->val;
insert(t->ch[dir], x);
if (t->ch[dir]->key < t->key) rotate(t, dir);
else t->update();
}
void insert(int x) { insert(root, x); }
void mergeto(node*& t, Treap* tr) {
if (t->ch[] != null) mergeto(t->ch[], tr);
if (t->ch[] != null) mergeto(t->ch[], tr);
tr->insert(t->val);
delete t; t = null;
}
void mergeto(Treap* tr) { mergeto(root, tr); }
int calckth(int k) {
if (k <= || k > root->sz) return INT_MIN;
bool dir;
for (node* t = root; t != null; t = t->ch[dir]) {
int cnt = t->ch[]->sz;
if (k == cnt+) return t->val;
else if (k <= cnt) dir = ;
else dir = , k -= (cnt+);
}
}
}**treap = new Treap*[maxn];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unionn1(int& x, int& y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
fa[x] = y; sz[y] += sz[x];
}
void unionn2(int x, int y) {
unionn1(x, y);
treap[x]->mergeto(treap[y]);
}
int n, m, q;
void work() {
for (int i = ; i <= n; ++i) {
scanf("%d", &val[i]);
mp[val[i]] = i;
}
for (int i = ; i <= n; ++i) fa[i] = i, sz[i] = ;
for (int i = ; i < m; ++i) {
int u, v;
scanf("%d%d", &u, &v);
unionn1(u, v);
}
for (int i = ; i <= n; ++i) {
treap[i] = new Treap();
fa[i] = find(i);
}
for (int i = ; i <= n; ++i) {
treap[fa[i]]->insert(val[i]);
}
scanf("%d", &q);
while (q--) {
char c; int x, y;
scanf("\n%c%d%d", &c, &x, &y);
if (c == 'Q') {
int ans = treap[find(x)]->calckth(y);
printf("%d\n", ans == INT_MIN ? - : mp[ans]);
}
else unionn2(x, y);
}
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) work();
return ;
}