bzoj2733: [HNOI2012]永无乡启发式合并

地址：http://www.lydsy.com/JudgeOnline/problem.php?id=2733

题目：

2733: [HNOI2012]永无乡

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4059 Solved: 2167
[Submit][Status][Discuss]

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

思路：

　　启发式合并。

 /**************************************************************

     Problem: 2733

     User: weeping

     Language: C++

     Result: Accepted

     Time:4908 ms

     Memory:4436 kb

 ****************************************************************/

 #include <bits/stdc++.h>

 using namespace std;

 #define lc ch[x][0]

 #define rc ch[x][1]

 int n,m,q,f[];

 int fd(int x)

 {

     return f[x]==x?x:f[x]=fd(f[x]);

 }

 struct SplayTree

 {

     const static int maxn = 1e5 + ;

     int tot,root,ch[maxn][], key[maxn], val[maxn], sz[maxn], rev[maxn], fa[maxn];

     inline void init( int x, int ky, int v = , int par =  )

     {

         lc=rc=, fa[x]= par, key[x] = ky, val[x] = v, sz[x] = , rev[x] = ;

     }

     inline void init()

     {

         init( , ,  );

         sz[] = ;

         tot = root =  ;

     }

     inline void push_up(int x)

     {

         sz[x] = sz[lc] + sz[rc] + ;

     }

     inline void reverse(int x)

     {

         rev[x] ^= , swap( lc, rc);

     }

     inline void push_down(int x)

     {

         if(rev[x])

         {

             if(lc)  reverse(lc);

             if(rc)  reverse(rc);

             rev[x] = ;

         }

     }

     void rotate( int x)

     {

         int f = fa[x], gf = fa[f];

         int t1 = (ch[f][] == x), t2 = (ch[gf][] == f);

         if( gf ) ch[gf][t2] = x;

         fa[x] = gf, ch[f][t1] = ch[x][^t1], fa[ch[f][t1]] = f;

         ch[x][t1^] = f, fa[f] = x;

         push_up( f ), push_up( x );

     }

     void splay( int x, int tar )

     {

         for(int f = fa[x], gf = fa[f]; f != tar; rotate(x), f = fa[x], gf = fa[f])

         if(gf != tar)

             rotate( ((ch[f][] == x) == (ch[gf][] == f) )? f: x);

         if( !tar ) root = x;

     }

     void insert( int ky, int v)

     {

         int x = root, ls = root;

         while(x)

         {

             push_down(x);

             sz[x] ++, ls = x;

             x = ch[x][ky > key[x]];

         }

         init( ++tot, ky, v, ls);

         ch[ls][ky > key[ls]] = tot;

         splay( tot, );

     }

     int find( int ky)

     {

         int x = root;

         while(x)

         {

             push_down(x);

             if(key[x] == ky) break;

             x = ch[x][ky > key[x]];

         }

         if(x)   splay(x,);

         else x = -;

         return x;

     }

     // Delete Root

     void Delete()

     {

         if( !ch[root][] )

         {

             fa[ ch[root][] ] =  ;

             root = ch[root][];

         }

         else

         {

             int cur = ch[root][];

             while( ch[cur][] ) cur = ch[cur][];

             splay( cur, root );

             ch[cur][] = ch[root][];

             root = cur, fa[cur] = , fa[ch[root][]] = root;

             push_up( root );

         }

     }

     int kth( int k)

     {

         int x = root;

         if(sz[x] < k) return -;

         while(x)

         {

             push_down(x);

             if(k == sz[lc] + ) break;

             if(k > sz[lc])

                 k -= sz[lc] + , x = rc;

             else

                 x = lc;

         }

         if(x)   splay(x,);

         else x = -;

         return x;

     }

     int pred( void)

     {

         int x = root;

         if(!x || !lc)   return -;

         x = lc;

         while(rc)    push_down(x), x = rc;

         splay( x, );

         return x;

     }

     int succ( void)

     {

         int x = root;

         if(!x || !rc) return -;

         x = rc;

         while(lc)   push_down(x), x = lc;

         splay( x, );

         return x;

     }

     void debug( int x )

     {

         if( !x ) return;

         if(lc) debug( lc );

         printf("%d ", key[x] );

         if(rc) debug( rc );

     }

     void qinsert(int y)

     {

         int x = root, ls = root, ky = key[y];

         while(x)

             ls = x, x = ch[x][ky > key[x]];

         x = ls;

         ch[x][ky > key[x]] = y,fa[y] = x, sz[y] = ;

         splay(y, );

     }

     void qmerge(int x)

     {

         if(!x) return;

         int tl = lc, tr = rc;

         lc  = rc = ;

         qmerge(tl);

         qinsert(x);

         qmerge(tr);

     }

     void merge(int u,int v)

     {

         if(u == v) return ;

         if(sz[u]>sz[v]) swap(u,v);

         f[u] = v, splay( v, );

         qmerge(u);

     }

 } sp;

 int main(void)

 {

     scanf("%d%d",&n,&m);

     for(int i=,x;i<=n;i++)

         scanf("%d",&x),f[i]=i,sp.key[i]=x,sp.sz[i]=;

     for(int i=,u,v;i<=m;i++)

         scanf("%d%d",&u,&v),sp.merge(fd(u),fd(v));

     scanf("%d",&q);

     char op[];

     for(int i=,x,y;i<=q;i++)

     {

         scanf("%s%d%d",op,&x,&y);

         if(op[]=='B')

             sp.merge(fd(x),fd(y));

         else

             sp.splay(x,),printf("%d\n",sp.kth(y));

     }

     return ;

 }

永无乡