自动搬运

查看原文

来自洛谷，原作者为

	Romeolong **

搬运于2025-08-24 21:46:40，当前版本为作者最后更新于2018-09-14 15:55:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以线段树合并啊QwQ

为什么要Splay啊

多难写QwQ

可以对于每一个点动态开点线段树，维护重要度。然后用并查集维护联通性，每次连边或者Build就把两棵线段树合并就好了啊QwQ

至于Query操作，就看看左儿子的sum与k的关系就好了

跑得还挺快

下面是代码

#include<cstdio>
#define N (200010)
using namespace std;
inline int read(int &data){
    data=0;char ch=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();
    return data;
}
struct xds{
	int l,r,sum,ch[2];
}t[N<<5];
int n,m,ind,T[N],fa[N],ans[N];
int ask(int x){return (fa[x]==x)?x:fa[x]=ask(fa[x]);}
int insert(int p,int l,int r){
	int rt=++ind;
	t[rt].l=l,t[rt].r=r,t[rt].sum=1;
	if(l==r)return rt; int mid=(l+r)>>1;
	if(p>mid)t[rt].ch[1]=insert(p,mid+1,r);
	else t[rt].ch[0]=insert(p,l,mid);
	return rt;
}
int unite(int L,int R,int l,int r){
	if(!L&&!R)return 0;
	if(!L)return R; if(!R)return L;
	int rt=++ind,mid=(l+r)>>1;
	t[rt].l=l,t[rt].r=r,t[rt].sum=t[L].sum+t[R].sum;
	t[rt].ch[0]=unite(t[L].ch[0],t[R].ch[0],l,mid);
	t[rt].ch[1]=unite(t[L].ch[1],t[R].ch[1],mid+1,r);
	return rt;
}
int query(int x,int k){
	if(t[x].sum<k)return -1;
	if(t[x].l==t[x].r)return ans[t[x].l];
	if(t[t[x].ch[0]].sum>=k)return query(t[x].ch[0],k);
	else return query(t[x].ch[1],k-t[t[x].ch[0]].sum);
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++){fa[i]=i; int x;read(x),T[i]=insert(x,1,n),ans[x]=i;}
	for(int i=1;i<=m;i++){
		int x,y; read(x),read(y);
		int p=ask(x),q=ask(y);
		if(p!=q)fa[p]=q,T[q]=unite(T[p],T[q],1,n);
	}
	int Q; read(Q);
	while(Q--){
		int x,y; char c;
		c=getchar(); while(c!='B'&&c!='Q')c=getchar();
		read(x),read(y); if(c=='Q')printf("%d\n",query(T[ask(x)],y));
		else{int p,q;p=ask(x),q=ask(y);if(p!=q)fa[p]=q,T[q]=unite(T[p],T[q],1,n);}
	}
}