2733: [HNOI2012]永无乡

题解：

爬到了bzoj的数据哈哈哈哈

然后提交上去t了 自己测只有1秒多呀 不理解

然后这题目就是个线段树/平衡树合并裸题

来练一下线段树合并 据说是nlogn的

#include <bits/stdc++.h>

using namespace std;

const int N=2e5;

#define rg register

#define IL inline

int n,m,fa[N],a[N],b[N],cnt,root[N],count2[N*],ls[N*],rs[N*];

bool f[N];

int find(rg int x)

{

    rg int tmp;

    if (fa[x]!=x) tmp=find(fa[x]);

    else return(x);

    fa[x]=tmp;

    return(tmp);

}

IL void link(rg int x,rg int y)

{

  x=find(x),y=find(y);

  if (x!=y) fa[x]=y;

}

#define mid (h+t)/2

void insert(int &x,int goal,int h,int t)

{

    if (!x) x=++cnt;

    count2[x]++;

    if (h==t) return;

    if (goal<=mid) insert(ls[x],goal,h,mid);

    else insert(rs[x],goal,mid+,t);

}

int query(int x,int y,int h,int t)

{

    if (h==t)

      if (y==&&x!=) return(h); else return();

  if (count2[ls[x]]<y) return(query(rs[x],y-count2[ls[x]],mid+,t));

  else return(query(ls[x],y,h,mid));

}

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]);

    count2[x]=count2[ls[x]]+count2[rs[x]];

    return(x);

}

int main()

{

    freopen("noi.in","r",stdin);

    freopen("noi.out","w",stdout);

    ios::sync_with_stdio(false);

    cin>>n>>m;

    for (rg int i=;i<=n;i++) cin>>a[i],b[a[i]]=i,fa[i]=i;

    for (rg int i=;i<=m;i++)

    {

        int x,y;

        cin>>x>>y;

        link(x,y);

    }

    for (rg int i=;i<=n;i++)

    {

        int x=find(i);

      insert(root[x],a[i],,N);

  }

  int qt;

  cin>>qt;

  b[]=-;

    for (rg int i=;i<=qt;i++)

    {

         int x,y;

         char cc;

         cin>>cc;

         cin>>x>>y;

         if (cc=='Q')

         {

              x=find(x);

              int t=query(root[x],y,,N);

              cout<<b[query(root[x],y,,N)]<<endl;

         }

         if (cc=='B')

         {

              x=find(x); y=find(y);

              if (x!=y)

              {

                   fa[x]=y;

                   root[y]=merge(root[x],root[y]);

             }

         }

    }

    return ;

}