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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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<a[k].val)
{
insert(a[k].lson,temp);update(k);
if(a[a[k].lson].rnd<a[k].rnd) rturn(k);
}
else
{
insert(a[k].rson,temp);update(k);
if(a[a[k].rson].rnd<a[k].rnd) lturn(k);
}
}
void del(int &k,int temp)
{
if(!k) return;
if(temp==a[k].val)
{
if(a[k].num>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].rson].rnd)
{
rturn(k);
del(k,temp);
}
else
{
lturn(k);
del(k,temp);
}
}
else if(temp<a[k].val)
{
a[k].size--;
del(a[k].lson,temp);
}
else
{
a[k].size--;
del(a[k].rson,temp);
}
}
int ask_num(int k,int temp)
{
if(k<=0||temp<=0) return 0;
if(temp<=a[a[k].lson].size) return ask_num(a[k].lson,temp);
else if(temp>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... ...