【bzoj2733】[HNOI2012]永无乡 启发式合并

2015.05.23 12:46 Sat | 17次阅读 | 旧日oi | 固定链接 | 源码

题目大意:给定一些点,每个点有不同权值,有两种操作,1:连接连个点;2:询问x所在的联通块中权值第k小的点,数据范围n<=100000,操作数<=300000
题解
启发式合并的裸题,对每个联通块维护一个treap。对于每个合并操作,把元素少的联通块暴力加到元素多的联通块中,这样做的话因为每次被拆解的联通块合并之后大小都会大于等于原来的二倍,所以每个点最多被加入了logn次,总的复杂度也就是nlgn。

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 1000005
int n,m,cnt,q;
char s[5];
int rank[N],fa[N],root[N];
int siz[N],rnd[N],val[N],ls[N],rs[N],d[N],tot;
bool vis[N];
struct edge{
    int to,next,val;
}e[N<<2];
int h[N],tp;
void update(int x)
{
    siz[x]=siz[ls[x]]+siz[rs[x]]+1;
}
void lturn(int &k)
{
    int t=rs[k];rs[k]=ls[t];ls[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void rturn(int &k)
{
    int t=ls[k];ls[k]=rs[t];rs[t]=k;
    siz[t]=siz[k];update(k);k=t;
}
void insert(int &x,int pos)
{
    if(!x) 
    {
        if(tot) x=d[tot--];
        else x=++cnt;
        val[x]=pos;
        siz[x]=1;
        ls[x]=rs[x]=0;
        rnd[x]=rand();
        return;
    }
    siz[x]++;
    if(rank[val[x]]<rank[pos])
    {
        insert(rs[x],pos);
        if(rnd[rs[x]]<rnd[x]) lturn(x);
    }
    else
    {
        insert(ls[x],pos);
        if(rnd[ls[x]]<rnd[x]) rturn(x);
    }
}
int query(int x,int t)
{
    while(x)
    {
        if(siz[ls[x]]>=t) x=ls[x];
        else if(siz[ls[x]]+1==t) return val[x];
        else t-=siz[ls[x]]+1,x=rs[x];
    }
    return -1;
}
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void dfs(int rt,int u,int f)
{
    insert(root[rt],u);
    fa[u]=rt;vis[u]=1;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    if((v=e[i].to)!=f) dfs(rt,v,u);
}
void combine(int &x,int y)
{
    insert(x,val[y]);
    if(ls[y]) combine(x,ls[y]);
    if(rs[y]) combine(x,rs[y]);
    d[++tot]=y;
}
int main()
{
    //freopen("tt.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&rank[i]),fa[i]=i;
    for(int u,v,i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        ae(u,v);ae(v,u);
    }
    for(int i=1;i<=n;i++) 
    if(!vis[i]) dfs(i,i,0);
    cin>>q;int o=0;
    for(int x,y,i=1;i<=q;i++)
    {
        scanf("%s",s);
        if(s[0]=='B')
        {
            scanf("%d%d",&x,&y);
            int p=find(x),q=find(y);
            if(p==q) continue;
            if(siz[root[q]]>siz[root[p]]) swap(p,q);
            combine(root[p],root[q]);fa[q]=p;
        }
        else
        {
            o++;
            scanf("%d%d",&x,&y);
            printf("%d\n",query(root[find(x)],y));
        }
    }
}```