2733: [HNOI2012]永无乡
Time Limit: 20 Sec
Memory Limit: 256 MB
题目连接
http://www.lydsy.com/JudgeOnline/problem.php?id=2733
Description
永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可 以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连 通的。现在有两种操作：B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座，请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作，该部分的第一行是一个正整数 q， 表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000
对于 100%的数据 n≤100000,m≤n，q≤300000
Output
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表 示所询问岛屿的编号。如果该岛屿不存在，则输出-1。
Sample Input
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
Sample Output
-1
2
5
1
2
HINT
题意
题解：
启发式合并treap，直接套版咯。。。
合并就用并查集来维护，如果不在的话，就强行把小的treap直接暴力insert到大的treap里面就好了
然后再找第k大就好了
代码
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<algorithm>
#include<ctime>
using namespace std; #define maxn 100005
int n,m,q;
//////////////////////////////////////////////
struct TreeNode {
TreeNode *L, *R;
int num;
int size;
int pri;
int key;
};
TreeNode nodes[maxn*], stack[maxn*];
TreeNode *null;
int C, Top; void init() {
C = ; Top = ;
null = &nodes[C++];
null->L = null->R = null;
null->pri = -0x7FFFFFFF;
null->size = ;
null->key = ;
null->num = ;
} struct Treap { TreeNode* root;
vector<TreeNode*> list; void init() {
root = null;
} void toArrayList(TreeNode* root) {
if (root != null) {
toArrayList(root->L);
list.push_back(root);
toArrayList(root->R);
}
} TreeNode* newNode(int key, int num) {
TreeNode* ret;
if (Top)
ret = &stack[--Top];
else ret = &nodes[++C];
ret->L = ret->R = null;
ret->key = key;
ret->pri = rand();
ret->num = num;
ret->size = num;
return ret;
} TreeNode* merge(TreeNode* A , TreeNode* B) {//合并
if (A == null)
return B;
if (B == null)
return A;
if (A->pri < B->pri) {
A->R = merge(A->R, B);
pushUp(A);
return A;
} else {
B->L = merge(A, B->L);
pushUp(B);
return B;
}
} pair<TreeNode*, TreeNode*> split(TreeNode* root, int key) {//分裂
pair<TreeNode*, TreeNode*> tmp;
if (root == null) {
tmp = make_pair(null, null);
return tmp;
}
if (key <= root->key) {
tmp = split(root->L, key);
root->L = tmp.second;
pushUp(root);
tmp.second = root;
return tmp;
} else {
tmp = split(root->R, key);
root->R = tmp.first;
pushUp(root);
tmp.first = root;
return tmp;
}
} TreeNode* upperBound(TreeNode* root, int key) {
TreeNode* ans = null;
TreeNode* i = root;
while (i != null) {
if (key < i->key) {
ans = i;
i = i->L;
} else {
i = i->R;
}
}
return ans;
} TreeNode* lowerBound(TreeNode* root, int key) {
TreeNode* ans = null;
TreeNode* i = root;
while (i != null) {
if (key < i->key) {
i = i->L;
} else {
ans = i;
i = i->R;
}
}
return ans;
} bool contains(TreeNode* root, int key) {
if (root == null)
return false;
if (key == root->key)
return true;
else if (key < root->key)
return contains(root->L, key);
else
return contains(root->R, key);
} void insert(TreeNode* root, int key, int num) {
if (key < root->key)
insert(root->L, key, num);
else if (key == root->key)
root->num += num;
else
insert(root->R, key, num);
pushUp(root);
} void insert(int key, int num) {
if (contains(root, key)) {
insert(root, key, num);
return ;
}
pair<TreeNode*, TreeNode*> tmp = split(root, key);
TreeNode* node = newNode(key, num);
root = merge(merge(tmp.first, node), tmp.second);
} void del(int key) {
pair<TreeNode*, TreeNode*> tmp = split(root, key);
TreeNode* node = upperBound(tmp.second, key);
if (node == null)
root = tmp.first;
else
root = merge(tmp.first, split(tmp.second, node->key).second);
} void del(TreeNode* root, int key) {
if (!contains(root, key))
return ;
if (key < root->key)
del(root->L, key);
else if (key == root->key) {
root->num--;
if (root->num == )
del(key);
} else {
del(root->R, key);
}
pushUp(root);
} TreeNode* select(TreeNode* root, int k) {
if (k <= root->L->size)
return select(root->L, k);
else if (k >= root->L->size + && k <= root->L->size + root->num)
return root;
else
return select(root->R, k-root->L->size-root->num);
} int getMin(TreeNode* root, int key) {
if (key < root->key)
return getMin(root->L, key);
else if (key == root->key)
return root->L->size + root->num;
else
return root->L->size + root->num + getMin(root->R, key);
} int getMax(TreeNode* root, int key) {
if (key < root->key)
return root->R->size + root->num + getMax(root->L, key);
else if (key == root->key)
return root->R->size + root->num;
else
return getMax(root->R, key);
} int size() {
return root->size;
} void visit(TreeNode* root) {
if (root != null) {
printf("key: %d num: %d size: %d\n", root->key, root->num, root->size);
visit(root->L);
visit(root->R);
}
} void pushUp(TreeNode* x) {
x->size = x->L->size + x->R->size + x->num;
}
}; //////////////////////////////////////
int fa[maxn];
Treap tr[maxn];
int val[maxn],Hash[maxn];
int fi(int x)
{
if(x!=fa[x])fa[x]=fi(fa[x]);
return fa[x];
}
void uni(int x,int y)
{
x = fi(x),y = fi(y);
if(x!=y)
{
if(tr[x].size()>tr[y].size())
swap(x,y);
fa[x]=y;
tr[x].list.clear();
tr[x].toArrayList(tr[x].root);
for(int i=;i<tr[x].list.size();i++)
{
TreeNode* tmp = tr[x].list[i];
tr[y].insert(tmp->key,tmp->num);
}
}
}
int query(int x,int k)
{
x = fi(x);
if(tr[x].size()<k)return -;
else return tr[x].select(tr[x].root,k)->key;
}
int main()
{
init();
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
tr[i].init();
fa[i]=i;
scanf("%d",&val[i]);
Hash[val[i]]=i;
tr[i].insert(val[i],);
}
for(int i=;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
uni(x,y);
}
scanf("%d",&q);
for(int i=;i<q;i++)
{
char s[];
scanf("%s",&s);
int x,y;scanf("%d%d",&x,&y);
if(s[]=='B')
{
uni(x,y);
}
else
{
int p = query(x,y);
if(p==-)printf("-1\n");
else printf("%d\n",Hash[p]);
}
}
}