题解 P3224 【[HNOI2012]永无乡】

破壁人 · 2018-05-21 10:37:16 · 题解

分析： 首先我们可以用并查集来维护点的连通关系。

  对于询问，我们可以把同一连通块中的节点都放在一颗splay中

  然后就是求一颗splay中的第k小。

  然后建n棵一个节点的splay，在连边的过程中不断合并两颗splay(启发式合并)

  注意splay中的查询操作要尽量用非递归形式，否则会T。

代码:

#include<iostream>
#include<cstdio>

using namespace std;

struct t
{
    int fa,ch[2],val,size;
}sbt[500001];

int n,m,ff[500001],a[500001],root[500001];

void update(int o){sbt[o].size=sbt[sbt[o].ch[0]].size+sbt[sbt[o].ch[1]].size+1;}

int find(int o) {return (o==ff[o])?o:ff[o]=find(ff[o]);}

int Find(int o,int p)
{
    while(1)
    {
        if(o==0) return -1;
        if(sbt[sbt[o].ch[0]].size<p) {p=p-sbt[sbt[o].ch[0]].size-1;o=sbt[o].ch[1];}else
        if(sbt[sbt[o].ch[0]].size>p) o=sbt[o].ch[0];else return sbt[o].val;
    }
}

void rotate(int o)
{
    int x=o,y=sbt[x].fa,z=sbt[y].fa;
    int k=sbt[y].ch[1]==x;
    sbt[z].ch[y==sbt[z].ch[1]]=x;
    sbt[x].fa=z;sbt[y].fa=x;
    sbt[y].ch[k]=sbt[x].ch[k^1];
    sbt[sbt[x].ch[k^1]].fa=y;
    sbt[x].ch[k^1]=y;
    update(y);update(x);
}

void splay(int o,int p)
{
    while(sbt[o].fa!=p)
    {
        int x=o,y=sbt[x].fa,z=sbt[y].fa;
        if(z!=p)
            ((x==sbt[y].ch[0])==(y==sbt[x].ch[0]))?rotate(y):rotate(x);
        rotate(x);
    }
    if(p==0) root[find(o)]=o;
}

void insert(int o,int p)
{
    int y=p,k1=0;
    while(y!=0)
        if(o<y) {k1=y;y=sbt[y].ch[0];}else {k1=y;y=sbt[y].ch[1];}
    y=k1;
    sbt[o].fa=y;sbt[o].ch[0]=sbt[o].ch[1]=0;
    sbt[o].size=1;
    if(y<o) sbt[y].ch[1]=o;else sbt[y].ch[0]=o;
    update(y);
    splay(o,0);
}

void charu(int o,int p)
{
    if(o==0) return;
    charu(sbt[o].ch[0],p);
    charu(sbt[o].ch[1],p);
    insert(o,p);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        ff[a[i]]=a[i];
        sbt[a[i]].fa=sbt[a[i]].ch[0]=sbt[a[i]].ch[1]=0;
        sbt[a[i]].val=i;
        sbt[a[i]].size=1;
        root[a[i]]=a[i];
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int xx=find(a[x]),yy=find(a[y]);
        if(sbt[root[xx]].size>sbt[root[yy]].size) swap(xx,yy);
        charu(root[xx],root[yy]);ff[yy]=xx;
    }
    int Q;
    cin>>Q;
    while(Q--)
    {
        char ch[5];int x,y;
        scanf("%s%d%d",ch,&x,&y);
        if(ch[0]=='Q') 
        {
            int xc=find(a[x]);
            splay(a[x],0);
            printf("%d\n",Find(root[xc],y-1));
        }
        if(ch[0]=='B')
        {
            int xx=find(a[x]),yy=find(a[y]);
            if(sbt[root[xx]].size>sbt[root[yy]].size) swap(xx,yy);
            charu(root[xx],root[yy]);ff[yy]=xx;
        }
    }
    return 0;
}