洛谷 P3224 [HNOI2012]永无乡 题解

• 查询第 \(k\) 小值想到权值线段树。
• 合并操作想到线段树合并。
• 维护连通性想到并查集。
• 并查集合并方向应与线段树合并方向一致。
• 查询时，先求出并查集的根再在线段树上询问。

/*
 * Title: P3224 [HNOI2012]永无乡
 * Source: 洛谷
 * URL: https://www.luogu.com.cn/problem/P3224
 * Author: Steven_lzx
 * Command: -std=c++23 -Wall -fno-ms-extensions
 * Date: 2022.10.19
 */
#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=100010;
int n,m,q;
namespace UFS
{
    int fa[MAXN];
    int find(int x){return (x==fa[x]?x:fa[x]=find(fa[x]));}
}
using namespace UFS;
namespace SEGT
{
    int idx,root[MAXN],ls[MAXN<<5],rs[MAXN<<5],id[MAXN<<5],sum[MAXN<<5];
    void update(int &p,int l,int r,int k,int c)
    {
        int mid;
        if(!p)
            p=++idx;
        if(l==r)
        {
            id[p]=c;
            sum[p]++;
            return;
        }
        mid=(l+r)>>1;
        if(k<=mid)
            update(ls[p],l,mid,k,c);
        else
            update(rs[p],mid+1,r,k,c);
        sum[p]=sum[ls[p]]+sum[rs[p]];
        return;
    }
    int query(int p,int l,int r,int k)
    {
        int res,mid;
        if(sum[p]<k||!p)
            return 0;
        if(l==r)
            return id[p];
        mid=(l+r)>>1;
        if(k<=sum[ls[p]])
            res=query(ls[p],l,mid,k);
        else 
            res=query(rs[p],mid+1,r,k-sum[ls[p]]);
        return res;
    }
    void merge(int &p,int q,int l,int r)
    {
        int mid;
        if(!q)
            return;
        if(!p)
        {
            p=q;
            return;
        }
        if(l==r)
        {
            if(id[q])
            {
                id[p]=id[q];
                sum[p]+=sum[q];
            }
            return;
        }
        mid=(l+r)>>1;
        merge(ls[p],ls[q],l,mid);
        merge(rs[p],rs[q],mid+1,r);
        sum[p]=sum[ls[p]]+sum[rs[p]]; 
        return;
    }
}
using namespace SEGT;
int main()
{
    int l,r,ans;
    char s[10];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        scanf("%d",&l);
        update(root[i],1,n,l,i);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        l=find(l);
        r=find(r);
        fa[r]=l;
        merge(root[l],root[r],1,n);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%s %d %d",s,&l,&r);
        //cout<<s<<endl;
        if(s[0]=='B')
        {
            l=find(l);
            r=find(r);
            if(l==r)
                continue;
            fa[r]=l;
            merge(root[l],root[r],1,n);
        }
        else if(s[0]=='Q')
        {
            l=find(l);
            ans=query(root[l],1,n,r);
            if(!ans)
                ans=-1;
            printf("%d\n",ans);
        }
    }
    return 0;
}