首先连通块我们用并查集维护，而查询k大我们用权值线段树维护
建边就是合并两个线段树
查询直接在权值线段树查询就好了
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,q,a[100005],f[100005],v[100005],root[100005],cnt;
struct SegTree{
int nl,nr,sum;
}tree[2000005];
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Insert(int &rt,int l,int r,int pos){
if(!rt)rt=++cnt;
if(l==r){tree[rt].sum=1;return;}
int mid=l+r>>1;
if(pos<=mid)Insert(tree[rt].nl,l,mid,pos);
else Insert(tree[rt].nr,mid+1,r,pos);
tree[rt].sum=tree[tree[rt].nl].sum+tree[tree[rt].nr].sum;
}
int Query(int rt,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1;
if(tree[tree[rt].nl].sum>=k)return Query(tree[rt].nl,l,mid,k);
return Query(tree[rt].nr,mid+1,r,k-tree[tree[rt].nl].sum);
}
int Merge(int l,int r){
if(!l)return r;
if(!r)return l;
tree[l].nl=Merge(tree[l].nl,tree[r].nl);
tree[l].nr=Merge(tree[l].nr,tree[r].nr);
tree[l].sum=tree[tree[l].nl].sum+tree[tree[l].nr].sum;
return l;
}
int main(){
freopen("2733.in","r",stdin);
freopen("2733.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i]=i;}
for(int i=1;i<=m;i++){
int tp,tq;
scanf("%d %d",&tp,&tq);
tp=Find(tp);tq=Find(tq);f[tp]=tq;
}
for(int i=1;i<=n;i++){Insert(root[Find(i)],1,n,a[i]);v[a[i]]=i;}
scanf("%d",&q);
while(q--){
char s[5];
int x,y;
scanf("%s %d %d",s,&x,&y);
if(s[0]=='B'){x=Find(x);y=Find(y);if(x!=y){f[x]=y;root[y]=Merge(root[x],root[y]);}}
if(s[0]=='Q'){x=Find(x);if(tree[root[x]].sum>=y)printf("%d\n",v[Query(root[x],1,n,y)]);else puts("-1");}
}
return 0;
}
评论 (0)
