题解 P3224 【[HNOI2012]永无乡】

减维 · 2017-11-25 12:03:29 · 题解

看到题解里面一堆权值线段树。。。

不行我要告诉自己这是一道平衡树的题！

于是我就是要写平衡树！

然而又一看题解

竟然没有用fhq Treap做的

于是赶紧来上一发

思路：

fhq Treap加启发式合并，每次把小树节点拆下来加到大树上

但是其实不用新建节点，也不用写队列，直接把son清空即可，然后再加进去

代码：

//by 减维
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<bitset>
#include<algorithm>
#define ll long long
#define maxn 100005
using namespace std;
int n,m,asd,cnt,rt[maxn],sz[maxn],siz[maxn],son[maxn][2],pri[maxn],val[maxn],ys[maxn];
int find(int x)
{
    if(rt[x]==x)return x;
    rt[x]=find(rt[x]);
    return rt[x];
}
void upda(int x)
{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void spli(int now,int k,int &x,int &y)
{
    if(!now)x=y=0;
    else{
        if(val[now]<=k)
            x=now,spli(son[now][1],k,son[now][1],y);
        else
            y=now,spli(son[now][0],k,x,son[now][0]);
        upda(now);
    }
}
int merge(int x,int y)
{
    if(!x||!y)return x+y;
    if(pri[x]<pri[y])
    {
        son[x][1]=merge(son[x][1],y);
        upda(x);
        return x;
    }else{
        son[y][0]=merge(x,son[y][0]);
        upda(y);
        return y;
    }
}
void insert(int &root,int x)
{
    int a,b;
    int v=val[x];
    spli(root,v,a,b);
    root=merge(merge(a,x),b);
}
void dfs(int x,int &y)
{
    if(!x)return ;
    dfs(son[x][0],y);
    dfs(son[x][1],y);
    son[x][0]=son[x][1]=0;
    insert(y,x);
}
int hebing(int x,int y)
{
    if(siz[x]>siz[y])swap(x,y);
    dfs(x,y);
    return y;
}
int kth(int now,int k)
{
    while(1)
    {
        if(k<=siz[son[now][0]])
            now=son[now][0];
        else if(k==siz[son[now][0]]+1)
            return now;
        else
            k-=siz[son[now][0]]+1,now=son[now][1];
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)scanf("%d",&val[i]),rt[i]=i,pri[i]=rand(),siz[i]=sz[i]=1,ys[val[i]]=i;
    cnt=n;
    for(int i=1,a,b,c;i<=m;++i)
    {
        scanf("%d%d",&a,&b);
        if(find(a)==find(b))continue;
        c=hebing(rt[a],rt[b]);
        rt[find(a)]=rt[find(b)]=c;
        rt[c]=c;
    }
    scanf("%d",&asd);
    char ch[5];
    for(int i=1,a,b,c;i<=asd;++i)
    {
        scanf("%s%d%d",ch,&a,&b);
        if(ch[0]=='B'){
            if(find(a)==find(b))continue;
            c=hebing(rt[a],rt[b]);
            rt[find(a)]=rt[find(b)]=c;
            rt[c]=c;
        }else{
            if(siz[find(a)]<b){
                printf("-1\n");
                continue;
            }
            printf("%d\n",ys[val[kth(find(a),b)]]);
        }
    }
    return 0;
}