The k-th Largest Group poj-2985

　　　　题目大意：给你n只猫，有两种操作：1.将两只猫所在的小组合并。2.查询小组数第k大的小组的猫数。

　　　　注释：1<=n,m<=200,000.

　　　　　　想法：开始的想法就是用Treap合并，用Treap删除。然后发现Treap合并实在是...太tm gay了。没办法，用并查集吧。想法就出现了，我们用并查集合并，用Treap查询k大值。考虑怎么实现：因为我们想用Treap查询k大值，所以我们Treap中维护的一定是集合中猫的个数。并查集的合并呢？我们可以只在并查集森林的根节点处维护每一颗并查集的节点数。用并查集直接合并就行，我们考虑如何进行Treap中的修改？我们可以先把两只猫的集合先删掉，然后在加入一个两只猫集合总数的节点即可。那么，这题就切了吗对不对... ...

　　　　最后，附上丑陋的代码... ...

#include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int tot,root;int number[400010];int fa[400010];struct Node{	int lson,rson;	int size,num;	int val,rnd;}a[400010];inline void update(int k){	a[k].size=a[a[k].lson].size+a[a[k].rson].size+a[k].num;}void lturn(int &k){	int t=a[k].rson;	a[k].rson=a[t].lson;	a[t].lson=k;	update(k);update(t);k=t;}void rturn(int &k){	int t=a[k].lson;	a[k].lson=a[t].rson;	a[t].rson=k;	update(k);update(t);k=t;}void insert(int &k,int temp){	if(!k)	{		k=++tot;		a[k].num=a[k].size=1;		a[k].val=temp;		a[k].rnd=rand();		return;	}	a[k].size++;	if(temp==a[k].val) a[k].num++;	else if(temp
         
          1)		{			a[k].num--;			a[k].size--;		}		else if(a[k].lson==0||a[k].rson==0)		{			k=a[k].lson+a[k].rson;		}		else if(a[a[k].lson].rnd
          
           a[a[k].lson].size+a[k].num) { return ask_num(a[k].rson,temp-a[k].num-a[a[k].lson].size); } else return a[k].val;}int find(int x){ return fa[x]==x?x:(fa[x]=find(fa[x]));}void merge(int x,int y){ x=find(x);y=find(y); fa[x]=y; number[y]+=number[x];}void original(){ memset(a,0,sizeof a); root=0; tot=0;}int main(){ int n,m; while(~scanf("%d%d",&n,&m)) { original(); for(int i=1;i<=n;i++) { fa[i]=i; number[i]=1; } root=1; tot=1; a[1].val=1; a[1].size=a[1].num=n; a[1].rnd=rand(); int flag; int x,y; for(int i=1;i<=m;i++) { scanf("%d",&flag); if(!flag) { scanf("%d%d",&x,&y); if(find(x)==find(y)) continue; del(root,number[find(x)]); del(root,number[find(y)]); insert(root,number[find(x)]+number[find(y)]); merge(x,y); } else { scanf("%d",&x); printf("%d\n",ask_num(root,a[root].size-x+1)); } } }}
          
         
        
       
      
     

 　　　　小结：我的并查集最后写错了，导致调了5h... ...