[BZOJ]2733 [HNOI2012]永无乡(线段树合并/splay启发式合并)

//模拟赛里一道题要启发式合并，但我没想出来，我记得以前写过，结果发现原来是用线段树合并做的。。。

线段树合并：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<string>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#include<vector>
typedef long long LL;
using namespace std;
const int N=100010;
int n,m,q,fa[N],root[N],ls[N<<6],rs[N<<6],sum[N<<6],id[N],rk[N],cnt;
char s[10];
int read() {int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;}
void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);}
int ask(int x){return fa[x]==x?x:fa[x]=ask(fa[x]);}
void insert(int &k,int l,int r,int x)
{
if (!k) k=++cnt;
    sum[k]++;
if (l==r) return;
int mid=(l+r)>>1;
if (x<=mid) insert(ls[k],l,mid,x);
else insert(rs[k],mid+1,r,x);
}
int query(int k,int l,int r,int x)
{
if (l==r) return l;
int mid=(l+r)>>1;
if (sum[ls[k]]>=x) return query(ls[k],l,mid,x);
else return query(rs[k],mid+1,r,x-sum[ls[k]]);
}
int merge(int x,int y)
{
if (!x) return y;
if (!y) return x;
    ls[x]=merge(ls[x],ls[y]);
    rs[x]=merge(rs[x],rs[y]);
    sum[x]=sum[ls[x]]+sum[rs[x]];
return x;
}
int main()
{
//judge();
    n=read(); m=read();
for (int i=1;i<=n;i++) fa[i]=i;
for (int i=1;i<=n;i++) rk[i]=read();
while (m--)
    {
int x=read(),y=read();
        fa[ask(x)]=ask(y);
    }
for (int i=1;i<=n;i++)
    {
        insert(root[ask(i)],1,n,rk[i]);
        id[rk[i]]=i;
    }
    q=read();
while (q--)
    {
        scanf("%s",s); int x=read(),y=read();
if (s[0]=='Q')
        {
int q=ask(x);
if (sum[root[q]]<y) {puts("-1"); continue;}
            printf("%d\n",id[query(root[q],1,n,y)]);
        }
else
        {
int q=ask(x),p=ask(y);
if (q!=p) fa[q]=p,root[p]=merge(root[p],root[q]);
        }
    }
return 0;
}

splay启发式合并：

#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pa;
const int N=100010;
int n,m,fa[N],f[N],c[N][2],siz[N],a[N],tmp,b[N],cnt;
//vector<int>e[N];
int Write[20],WRI;
inline void judge(){freopen(".in","r",stdin);freopen(".out","w",stdout);}
inline int read(){int d=0,f=1; char c=getchar(); while (c<'0'||c>'9'){if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=d*10+c-48,c=getchar(); return d*f;}
inline void write(int x){if (!x){putchar('0'); return;}if (x<0) putchar('-'),x=-x;for (WRI=1;x;x/=10,WRI++) Write[WRI]=x%10;for (int i=WRI-1;i;i--) putchar((char)(Write[i]+48));}
inline int ask(int x){return f[x]==x?x:f[x]=ask(f[x]);}
inline void update(int x){siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1;
if (y==k) k=x; else c[z][c[z][1]==y]=x;
    fa[c[x][r]]=y; fa[x]=z; fa[y]=x;
    c[y][l]=c[x][r]; c[x][r]=y;
    update(y); update(x);
}
inline void splay(int x,int &k)
{
while (x!=k)
    {
int y=fa[x],z=fa[y];
if (y!=k)
            c[y][0]==x^c[z][0]==y?rotate(x,k):rotate(y,k);
        rotate(x,k);
    }
}
inline void insert(int x,int y)
{
    c[y][0]=c[y][1]=0; siz[y]=1;
for (;;)
    {
if (a[y]<a[x])
        {
if (c[x][0]) x=c[x][0];
else
            {
                c[x][0]=y;
                fa[y]=x;
                splay(y,f[ask(x)]);
return;
            }
        }
else
if (c[x][1]) x=c[x][1];
else
            {
                c[x][1]=y;
                fa[y]=x;
                splay(y,f[ask(x)]);
return;
            }
    }
}
inline void dfs(int x)
{
if (c[x][0]) dfs(c[x][0]);
if (c[x][1]) dfs(c[x][1]);
    b[++cnt]=x;
}
inline void Unite(int x,int y)
{
    x=ask(x); y=ask(y);
if (x==y) return;
if (siz[x]<siz[y]) swap(x,y);
    cnt=0; dfs(y);
for (int i=1;i<=cnt;i++) insert(ask(x),b[i]);
}
inline int query(int x,int k)
{
int res=-1;
for (;x;)
    {
if (siz[c[x][0]]+1==k) {res=x; return res;}
if (siz[c[x][0]]>=k) x=c[x][0];
else k-=siz[c[x][0]]+1,x=c[x][1];
    }
return res;
}
int main()
{
//judge();
    n=read(); m=read();
for (int i=1;i<=n;i++) a[i]=read(),f[i]=i,siz[i]=1;
for (int i=1;i<=m;i++) Unite(read(),read());
    m=read();
while (m--)
    {
char s[2];
        scanf("%s",s);
int x=read(),y=read();
if (s[0]=='B') Unite(x,y);
else printf("%d\n",query(ask(x),y));
    }
return 0;
}