- 查询第 \(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;
}
标签:HNOI2012,int,题解,namespace,fa,MAXN,ls,P3224
From: https://www.cnblogs.com/2020gyk080/p/16808423.html