poj2985(名次树(treap))找第k大 The k-th Largest Group

2017年08月02日 10点热度 0人点赞 0条评论

  有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;
}

未经允许不得转载!poj2985(名次树(treap))找第k大 The k-th Largest Group

update

纸上得来终觉浅, 绝知此事须躬行。