题解 P3224 【[HNOI2012]永无乡】

Object_ · 2019-10-27 15:33:33 · 题解

基本思路：

• 权值线段树+线段树合并+并查集.

类似题目：

• 雨天的尾巴

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e7,INF=2e9;
struct Node{
    int ls,rs;
    int cnt;//被加次数
    int pos;//岛屿编号
}tr[MAXN];
int nodeCnt=0;//权值线段树
int root[MAXN];
void insert(int &now,int l,int r,int x,int pos){
    if(!now)now=++nodeCnt;
    if(l==r){
        tr[now].cnt++;
        tr[now].pos=pos;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)insert(tr[now].ls,l,mid,x,pos);
    else insert(tr[now].rs,mid+1,r,x,pos);
    tr[now].cnt=tr[tr[now].ls].cnt+tr[tr[now].rs].cnt;
}
int merge(int p,int q,int l,int r){
    if(!p)return q;
    if(!q)return p;
    if(l==r){
        tr[p].cnt+=tr[q].cnt;
        tr[p].pos=tr[q].pos;
        return p;
    }
    int mid=(l+r)>>1;
    tr[p].ls=merge(tr[p].ls,tr[q].ls,l,mid);
    tr[p].rs=merge(tr[p].rs,tr[q].rs,mid+1,r);
    tr[p].cnt=tr[tr[p].ls].cnt+tr[tr[p].rs].cnt;
    return p;
}
int query(int now,int l,int r,int k){
    if(l==r)return tr[now].pos;
    if(tr[now].cnt<k)return -1;//不存在
    int mid=(l+r)>>1;
    int lsum=tr[tr[now].ls].cnt;
    if(k<=lsum)return query(tr[now].ls,l,mid,k);
    else return query(tr[now].rs,mid+1,r,k-lsum);
}
int fa[MAXN];
int get(int x){
    while(x!=fa[x])x=fa[x]=fa[fa[x]];
    return x;
}
int b_merge(int a,int b){//集合合并
    fa[get(a)]=get(b);
    return get(b);
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(int i=1;i<=n;i++){
        int rank;//重要度
        scanf("%d",&rank);
        insert(root[i],-INF,INF,rank,i);
    }
    for(int i=1;i<=m;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        a=get(a),b=get(b);
        int rt=merge(root[a],root[b],-INF,INF);
        b_merge(a,b);
        root[a]=root[b]=rt;
    }
    int q;
    scanf("%d",&q);//q个操作
    for(int i=1;i<=q;i++){
        char opt;
        cin>>opt;
        if(opt=='B'){
            int x,y;
            scanf("%d%d",&x,&y);//修一条新桥
            x=get(x),y=get(y);
            int rt=merge(root[x],root[y],-INF,INF);
            b_merge(x,y);
            root[x]=root[y]=rt;
        }else if(opt=='Q'){
            int x,k;
            scanf("%d%d",&x,&k);
            cout<<query(root[get(x)],-INF,INF,k)<<endl;
        }
    }
    return 0;
}