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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define maxn 100005int n,m,q;//struct TreeNode { TreeNode *L, *R; int num; int size; int pri; int key;};TreeNode nodes[maxn*30], stack[maxn*5];TreeNode *null;int C, Top;void init() { C = 0; Top = 0; null = &nodes[C++]; null->L = null->R = null; null->pri = -0x7FFFFFFF; null->size = 0; null->key = 0; null->num = 0;}struct Treap { TreeNode* root; vector
           
             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
            
              split(TreeNode* root, int key) { //分裂 pair
             
               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
              
                tmp = split(root, key); TreeNode* node = newNode(key, num); root = merge(merge(tmp.first, node), tmp.second); } void del(int key) { pair
               
                 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 == 0) 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 + 1 && 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=0;i
                
                 key,tmp->num); } }}int query(int x,int k){ x = fi(x); if(tr[x].size()
                 
                  key;}int main(){ init(); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { tr[i].init(); fa[i]=i; scanf("%d",&val[i]); Hash[val[i]]=i; tr[i].insert(val[i],1); } for(int i=1;i<=m;i++) { int x,y;scanf("%d%d",&x,&y); uni(x,y); } scanf("%d",&q); for(int i=0;i