记录编号	146152	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	1.044 s
提交时间	2015-01-12 21:30:54	内存使用	1.08 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long LL;
typedef unsigned int Uint; 
const int INF=0x3fffffff;
//==============struct declaration==============
struct node{
  node *lc,*rc;
  int s,importance,no,fix;
  node(){lc=rc=NULL;s=1;fix=rand();}
};
//==============var declaration=================
const int MAXN=100010;
int n,m,q;
int root[MAXN];
node *Node[MAXN];
//==============function declaration============
int findr(int x){return root[x]==x?x:root[x]=findr(root[x]);}
void insert(node *&Tree,int importance,int no);
void merge(node *&Tree,node *&ins);
void Lrotate(node *&x);void Rrotate(node *&x);
void find_kth(node *&x,int rank);
void update(node *&x);
//==============main code=======================
int main()
{  
freopen("bzoj_2733.in","r",stdin);
freopen("bzoj_2733.out","w",stdout);
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++){
    root[i]=i;
    Node[i]=new(node);
    Node[i]->no=i;
    scanf("%d",&Node[i]->importance);
  }
  for(int i=1;i<=m;i++){
    int s,e;
    scanf("%d%d",&s,&e);
    if (findr(s)==findr(e))  continue;
    if (Node[findr(s)]->s<Node[findr(e)]->s)
      swap(s,e);//Make sure S is larger than E
    merge(Node[findr(s)],Node[findr(e)]);
	root[findr(e)]=findr(s);
  }
  scanf("%d",&m);
  while (m--){
    char cmd;
    scanf(" %c",&cmd);
    if (cmd=='B'){
      int s,e;
      scanf("%d%d",&s,&e);
      if (findr(s)==findr(e)) continue;
      if (Node[findr(s)]->s<Node[findr(e)]->s)
        swap(s,e);//Make sure S is larger than E
      merge(Node[findr(s)],Node[findr(e)]);
	  root[findr(e)]=findr(s);
	}
    else if (cmd=='Q'){
	  int no,k;
	  scanf("%d%d",&no,&k);
	  if (Node[findr(no)]->s<k){
	    printf("-1\n");
	    continue;
	  }
	  find_kth(Node[findr(no)],k);
    }
  }
  return 0;
}
//================fuction code====================
void update(node *&x){
  if (x==NULL) return;
  x->s=1;
  if (x->lc!=NULL)  x->s+=x->lc->s;
  if (x->rc!=NULL)  x->s+=x->rc->s;
}
void Lrotate(node *&x){
  node *y=x->lc;
  x->lc=y->rc;
  y->rc=x;
  x=y;
  update(x->rc);
  update(x);
}
void Rrotate(node *&x){
  node *y=x->rc;
  x->rc=y->lc;
  y->lc=x;
  x=y;
  update(x->lc);
  update(x);
}
void merge(node *&Tree,node *&ins){
  if (ins==NULL) return;
  merge(Tree,ins->lc);
  insert(Tree,ins->importance,ins->no);
  merge(Tree,ins->rc);
}
void insert(node *&Tree,int importance,int no){
  if (Tree==NULL){
    Tree=new(node);
    Tree->no=no;Tree->importance=importance;
	return;
  }
  if (importance<Tree->importance){
    insert(Tree->lc,importance,no);Tree->s++;
   // if (Tree->lc->fix<Tree->fix)
    //  Lrotate(Tree);
  }
  else{
    insert(Tree->rc,importance,no);Tree->s++;
   // if (Tree->rc->fix<Tree->fix)
    //  Rrotate(Tree);
  }
}
void find_kth(node *&x,int rank){
  int ls=0;
  if (x->lc!=NULL) ls=x->lc->s;
  if (ls+1==rank){
    printf("%d\n",x->no);
    return;
  }
  if (rank<=ls)
    find_kth(x->lc,rank);
  else
    find_kth(x->rc,rank-ls-1);
}