POJ 2985 并差集+SBT

题目大意：

有N只猫，M个操作。

操作种类如下：

0：把两只猫所在的组合并

1：数量第K大的组的数量是多少。

题目分析：

很容易想到用并差集合并组。但是至于那个第K大的组怎么求，可以用树状数组或者平衡树或者线段树。反正选一个用就好了。

插曲：

调了N久，发现delete操作之前没有真正理解。写错了。。。现在总算懂了。

实际上delete是会破坏SBT性质的。但是在插入的时候会修复。所以树的总高度将会是O(lgn)，其中n为插入操作执行的次数。

code:

#include #include #define N 200001
using namespace std;
struct treetype{int w,l,r,s;} tr[N*4];
int n,operate,f[N],tot,root,num[N];

void Left(int &p){
    int t=tr[p].r;
    tr[p].r=tr[t].l;
    tr[t].l=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void Right(int &p){
    int t=tr[p].l;
    tr[p].l=tr[t].r;
    tr[t].r=p;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    p=t;
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
}

void repair(int &p){
    bool flag=false;
    if (tr[tr[tr[p].l].l].s>tr[tr[p].r].s){
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].l].r].s>tr[tr[p].r].s){
        Left(tr[p].l);
        Right(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].r].s>tr[tr[p].l].s){
        Left(p);
        flag=true;
    }
    if (tr[tr[tr[p].r].l].s>tr[tr[p].l].s){
        Right(tr[p].r);
        Left(p);
        flag=true;
    }
    if (flag){
        repair(tr[p].l);
        repair(tr[p].r);
        repair(p);
    }
}

void ins(int &p,int w){
    if (p==0){
        tr[++tot].l=0;
        tr[tot].r=0;
        tr[tot].s=1;
        tr[tot].w=w;
        p=tot;
        return;
    }
    if (w<=tr[p].w) ins(tr[p].l,w);
               else ins(tr[p].r,w);
    tr[p].s=tr[tr[p].l].s+tr[tr[p].r].s+1;
    repair(p);
}

int del(int &p,int w){
    tr[p].s–;
    if (tr[p].w==w || tr[p].l==0 && w<=tr[p].w || tr[p].r==0 && w>tr[p].w){
        int delnum=tr[p].w;
        if (tr[p].l==0 || tr[p].r==0) p=tr[p].l+tr[p].r;
        else tr[p].w=del(tr[p].l,0x7FFFFFFF);
        return delnum;
    }
    if (w<=tr[p].w) return del(tr[p].l,w);
               else return del(tr[p].r,w);
}

int gf(int p){
    if (f[p]==p) return p;
    f[p]=gf(f[p]);
    return f[p];
}

int Find(int p,int k){
    if (tr[tr[p].r].s+1==k) return tr[p].w;
    if (tr[tr[p].r].s>=k) return Find(tr[p].r,k);
    return Find(tr[p].l,k-tr[tr[p].r].s-1);
}

void init(){
    tot=0; root=0;
    for (int i=1;i<=n;i++){
      f[i]=i;
      num[i]=1;
      ins(root,1);
    }
}

void work(){
    int op,x,y;
    for (int i=1;i<=operate;i++){
        scanf("%d",&op);
        if (op==0){
            scanf("%d%d",&x,&y);
            if (gf(x)==gf(y)) continue;
            if (num[f[x]]>num[f[y]]) swap(x,y);
            del(root,num[f[x]]);
            del(root,num[f[y]]);
            num[f[y]]+=num[f[x]];
            num[f[x]]=0;
            ins(root,num[f[y]]);
            f[f[x]]=f[y];
        }
        else{
            scanf("%d",&x);
            printf("%dn",Find(root,x));
        }
    }
}

int main(){
    scanf("%d%d",&n,&operate);
    init();
    work();
}