有N只猫,开始每只猫都是一个小组,下面要执行M个操作,操作0 i j 是把i猫和j猫所属的小组合并,操作1 k 是问你当前第k大的小组大小是多少. 且k<=当前的最大组数.这里要注意,如果K>Treap中的节点总数,就默认输出1.(因为我们Treap只保存了合并之后的组大小)
#include
struct Node {
Node *ch[2];
int r; //随机权值
int v; //值
int s; //附加域size
Node(int vv): v(vv) {
s = 1;
ch[0] = ch[1] = NULL;
r = rand();
}
int cmp(int x) const {
if(x == v) return -1;
return x < v ? 0 : 1;
}
void maintain() {
s = 1;
if(ch[0] != NULL) s += ch[0]->s;
if(ch[1] != NULL) s += ch[1]->s;
}
}*root;
void rotate(Node* &o, int d) { //旋转操作
Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
}
void insert(Node* &o, int x) { //插入操作
if(o == NULL) o = new Node(x);
else {
int d = x < o->v ? 0 : 1; //注意相等时处理方式可以改变
insert(o->ch[d], x);
if(o->ch[d]->r > o->r) rotate(o, d^1);
}
o->maintain();
}
void remove(Node* &o, int x) { //删除操作
int d = o->cmp(x);
Node* u = o;
if(d == -1) {
if(o->ch[0] != NULL && o->ch[1] != NULL){
int d2 = o->ch[0]->r > o->ch[1]->r ? 1 : 0;
rotate(o, d2);
remove(o->ch[d2], x);
}
else {
if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0];
delete u;
}
}
else remove(o->ch[d], x);
if(o != NULL) o->maintain();
}
int kth(Node* o, int k) {//找第k大
if(o == NULL || k > o->s || k <= 0) return 1;
int s = o->ch[1] == NULL ? 0 : o->ch[1]->s;
if(k == s+1) return o->v;
else if(k <= s) return kth(o->ch[1], k);
else return kth(o->ch[0], k-s-1);
}
#include
#include
#include
using namespace std;
const int mn=200005;
int n,m;
int f[mn],size[mn];
int find_set(int x)
{
int t=x;
while(x!=f[x]) x=f[x];
return f[t]=x;
}
int main(){
root=NULL;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
f[i]=i,size[i]=1;
while(m--)
{
int cmp;
scanf("%d",&cmp);
if(cmp)
{
int k;
scanf("%d",&k);
printf("%dn",kth(root,k));
}
else
{
int u,v;
scanf("%d%d",&u,&v);
int fx=find_set(u),fy=find_set(v);
if(fx!=fy)
{
if(size[fx]!=1) remove(root,size[fx]);
if(size[fy]!=1) remove(root,size[fy]);
f[fy]=fx;
size[fx]+=size[fy];
insert(root,size[fx]);
}
}
}
return 0;
}