P3224 [HNOI2012] 永无乡

2018-03-29 19:17:13


作为一个对平衡树几乎一窍不通的蒟蒻来说

这道题一看直接是懵逼的

还好有yyb大佬通俗易懂的题解

对于节点之间的连通性,考虑一个并查集来维护

这里采用启发式合并

启发式合并,即把size较小的平衡树合并到size较大的平衡树中

每一次合并时dfs遍历整个splay,把节点加入即可

查询时操作该节点所在集合的splay,找到第k小的值的编号即可

学到一招启发式合并(然而还是不会用)

我严重怀疑我是不是不适合平衡树

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define reg register
#define ls ch[now][0]
#define rs ch[now][1]
using namespace std;
const int N=3e5+5;
int n,m,tot,root[N],fa[N],f[N],h[N],val[N],size[N],ch[N][2];
inline int read()
{
    int x=0,w=1;
    char c=getchar();
    while (!isdigit(c)&&c!='-') c=getchar();
    if (c=='-') c=getchar(),w=-1;
    while (isdigit(c))
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*w;
}
inline bool get(int x)
{
    return ch[f[x]][1]==x;
}
inline void update(int now)
{
    size[now]=size[ls]+size[rs]+1;
}
inline void rotate(int x)//通俗易懂的旋转 
{
    int y=f[x],z=f[y],k=get(x),w=ch[x][k^1];
    ch[y][k]=w; if (w) f[w]=y;
    ch[x][k^1]=y; f[y]=x; f[x]=z;
    if (z) ch[z][ch[z][1]==y]=x;
    update(y); update(x);
}
inline void splay(int x,int k)
{
    while (f[x]!=k)
    {
        int y=f[x],z=f[y];
        if (z!=k) rotate(get(y)==get(x)?y:x);
        rotate(x);
    }
    if (k<=n) root[k]=x;
}
inline void insert(int x,int bh)//把x加入bh所在集合的splay 
{
    int now=root[bh],u=bh;
    while (now&&val[now]!=x)
      u=now,now=ch[now][x>val[now]];
    now=++tot; size[now]=1; f[now]=u;
    val[now]=x; ch[now][0]=ch[now][1]=0;
    if (u>n) ch[u][x>val[u]]=now;
    splay(now,bh);
}
void dfs(int now,int rt)//遍历整棵splay 
{
    if (ls) dfs(ls,rt);
    if (rs) dfs(rs,rt);
    insert(val[now],rt);
}
inline int findkth(int bh,int k)//在以bh为根的集合中找第k小 
{
    int now=root[bh];
    if (size[now]<k) return -1;
    while (1)
    {
        if (size[ls]>=k) now=ls;
        else if (size[ls]<k-1)
        {
            k-=size[ls]+1; now=rs;
        }
        else return val[now];
    }
}
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline void merge(int x,int y)
{
    x=getfa(x),y=getfa(y);
    if (x==y) return;
    if (size[root[x]]>size[root[y]]) swap(x,y);
    fa[x]=y; dfs(root[x],y);
}
int main()
{
    n=read(),m=read(); tot=(n<<1);
    for (reg int i=1;i<=n;i++)
      root[i]=i+n,fa[i]=i;
    for (reg int i=1;i<=n;i++)
    {
        int x=read(); h[x]=i;//x的位置 
        val[i+n]=x; size[i+n]=1; f[i+n]=i;
    }
    for (reg int i=1;i<=m;i++) merge(read(),read());
    for (reg int q=read();q;q--)
    {
        char opt[5]; scanf("%s",opt);
        int x=read(),y=read();
        if (opt[0]=='B') merge(x,y);
        else
        {
            int ans=findkth(getfa(x),y);
            printf("%d\n",ans==-1?ans:h[ans]);
        }
    }
    return 0;
}