日常[线段树]：水题记——永无乡

永无乡是传说中线段树合并的模板题目，结合了并查集实现集合的合并与查询。

经验什么的只有一点：任何返回值都有自己的意义。

 

所以我在认真的研究了本题的标程和模板代码后认真的打了一遍，死活不输出mdf搞得我上天无路入地无门叫天天不应叫地地不灵，*！。然后检查了大约20分钟，发现，find函数直接打爆了……*！（大佬不要笑），merge函数少一个最终的返回值然后死在了里面……*！

 

另外快读在大数据输入的题目中优化强大的一批，如下直降600毫：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define read(a) a=init()
using namespace std;
int n,m,q,father[100003],tot,root[100003];
struct node{
    int lc,rc,size;
}di[6000003];
int a[100003],x,y,z;
char ch;
inline int init()
{
    int a=0,b=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){a=(a<<3)+(a<<1)+(ch-'0');ch=getchar();}
    return a*b;
}
int find(int x)//并查集 
{
    if(father[x]==x)return x;
    return father[x]=find(father[x]);
}
inline void insert(int &root,int l,int r,int pos)
{
    root=++tot;
    di[root].size=1;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(pos<=mid)insert(di[root].lc,l,mid,pos);
    else insert(di[root].rc,mid+1,r,pos);
}
inline int merge(int xr,int yr,int l,int r)
{
    if(!xr||!yr)return xr+yr;
    di[xr].size+=di[yr].size;
    if(l==r)return xr;
    int mid=(l+r)>>1;
    di[xr].lc=merge(di[xr].lc,di[yr].lc,l,mid);
    di[xr].rc=merge(di[xr].rc,di[yr].rc,mid+1,r);
    return xr;
}
inline void b_fa(int x,int y)
{
    x=find(x),y=find(y);
    if(x!=y)
    {
        father[y]=x;
        root[x]=merge(root[x],root[y],1,n);
    }
}
inline int ask(int root,int l,int r,int k)
{
    if(l==r)return a[l];
    int mid=(l+r)>>1;
    if(di[di[root].lc].size>=k)ask(di[root].lc,l,mid,k);
    else ask(di[root].rc,mid+1,r,k-di[di[root].lc].size);
}
int main()
{
    read(n),read(m);
    for(register int i=1;i<=n;++i)
    {
        father[i]=i;
        read(x);a[x]=i;
        insert(root[i],1,n,x);
    }
    for(register int i=1;i<=m;++i)
    {
        read(x),read(y);
        b_fa(x,y);
    }
    read(q);
    for(register int i=1;i<=q;++i)
    {
        cin>>ch;
        read(x),read(y);
        if(ch=='B')
            b_fa(x,y);
        if(ch=='Q')
        {
            if(di[root[find(x)]].size<y)
            {
                printf("-1\n");
                continue;
            }
            else
            {
                printf("%d\n",ask(root[find(x)],1,n,y));
                continue;
            }
        }
    }
}