本文共 1541 字，大约阅读时间需要 5 分钟。

个人认为码风还是比较整洁的(作为线段树合并的代码,虽然常数巨大)

作为一个题一$A$题,还是非常愉悦的hhh

其实做法也比较显然

因为需要动态找到排名第$k$重要的

我们对每个点都维护一个权值线段树

然后并查集合并连通块的时候也顺便合并连通块

并且一定要合并到祖先的那个点上去

然后查询的时候,找到那个点的祖先，就算代表这个连通块的线段树

在树上二分查找即可

#include 
   
    using namespace std;#define mid (l+r>>1)const int maxn = 2e5+10; int n,m,q,th[maxn];//线段树数组int sum[maxn*100],ls[maxn*100],rs[maxn*100],root[maxn],id,fa[maxn]; void add(int &rt,int l,int r,int index){
   	if( !rt )	rt = ++id;	if( l==r ){
    sum[rt] = 1; return; }	if( mid>=index )	add(ls[rt],l,mid,index);	else	add(rs[rt],mid+1,r,index);	sum[rt] = sum[ls[rt]]+sum[rs[rt]];	}int ask(int &rt,int l,int r,int k){
   	if( !rt )	rt = ++id;	if( l==r )	return l;	if( sum[ls[rt]]>=k )	return ask(ls[rt],l,mid,k);	else	return ask(rs[rt],mid+1,r,k-sum[ls[rt]] );}int merge(int x,int y,int l,int r){
   	if( x==0||y==0 )	return x+y;	if( l==r ){
    sum[x]+=sum[y]; return x; }	ls[x] = merge(ls[x],ls[y],l,mid );	rs[x] = merge(rs[x],rs[y],mid+1,r );	sum[x] = sum[ls[x]]+sum[rs[x]];	return x;}int pre[maxn];int find(int x){
    return x==pre[x]?x:pre[x]=find( pre[x] ); }void join(int x,int y){
   	int fl = find(x), fr = find(y);	if( fl==fr )	return;	root[fr] = merge(root[fr],root[fl],1,n);	pre[fl] = fr;}signed main(){
   	cin >> n >> m;	for(int i=1;i<=n;i++)	{
   		cin >> th[i]; pre[i] = i; fa[th[i]] = i;		add(root[i],1,n,th[i] );	}	for(int i=1;i<=m;i++)	{
   		int l,r; cin >> l >> r;		join(l,r); 	}	cin >> q;	for(int i=1;i<=q;i++)	{
   		string op; int x,y;		cin >> op >> x >> y;		if( op[0]=='Q' )		{
   			int rt = root[find(x)];			if( sum[rt]
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113646186 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！