bzoj2733: [HNOI2012]永无乡

用并查集维护集合关系，同时用线段树查询

出现合并时，将线段树合并，类似左偏树

http://www.lydsy.com/JudgeOnline/problem.php?id=2733

/**************************************************************
    Problem: 2733
    User: 1349367067
    Language: C++
    Result: Accepted
    Time:2500 ms
    Memory:25884 kb
****************************************************************/
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100011
using namespace std;
int n,m;
int ls[N*20],rs[N*20],size[N*20],num;
int fa[N],No[N],c[N];
inline int findf(int x)
{
       if (x==fa[x]) return x;
       else return fa[x]=findf(fa[x]);
}
void build(int x,int l,int r,int a)
{
     if (l==r)
     {
              size[x]=1;return;
     }
     int mid=(l+r)/2;
     if (a<=mid)
     {
        num++;ls[x]=num;
        build(num,l,mid,a);
     }
     else
     {
        num++;rs[x]=num;
        build(num,mid+1,r,a);
     }
     size[x]=1;
}
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]);
    size[x]=size[ls[x]]+size[rs[x]];
    return x;
} 
int findx(int x,int l,int r,int a)
{
     if (l==r) return l;
     int mid=(l+r)/2;
     if (a<=size[ls[x]])
        return findx(ls[x],l,mid,a);
     else
        return findx(rs[x],mid+1,r,a-size[ls[x]]);
}
void init()
{
     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++)
         scanf("%d",&c[i]);
     for (int i=1;i<=n;i++)
         No[c[i]]=i;
     num=n;
     for (int i=1;i<=n;i++)
         build(i,1,n,c[i]);
     for (int i=1;i<=n;i++)
         fa[i]=i;
     int l,r;
     for (int i=1;i<=m;i++)
     {
         scanf("%d%d",&l,&r);
         l=findf(l);r=findf(r);
         if (l==r) continue;
         if (l>r) swap(l,r);
         fa[r]=l;
         merge(l,r);
     }
     int Q;
     char ch[10];
     scanf("%d",&Q);
     for (int i=1;i<=Q;i++)
     {
         scanf("%s",ch);
         if (ch[0]=='B')
         {
            scanf("%d%d",&l,&r);
            l=findf(l);r=findf(r);
            if (l==r) continue;
            if (l>r) swap(l,r);
            fa[r]=l;
            merge(l,r);
         }
         else
         {
            scanf("%d%d",&l,&r);
            l=findf(l);
            if (r>size[l]) printf("-1\n");
            else
               printf("%d\n",No[findx(l,1,n,r)]);
         }
     }
}
int main()
{
    init();
     
    return 0;
}      

View Code

转载于:https://www.cnblogs.com/3ZStarve/p/4896771.html