[HNOI2012]永无乡 线段树合并

[HNOI2012]永无乡 线段树合并

啥？平衡树？看我用权值线段树切了它

首先并查集维护联通块，然后合并联通块时即合并两个father的线段树，查询(k)大时直接上权值线段树。

注意动态开点。

#include <cstdio>
#define MAXN 100010
#define MAXM MAXN*18
using namespace std;
int fa[MAXN];
int n,m;
inline int read(){
    char ch=getchar();int s=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s;
}
int get_fa(int x){
    if(fa[x]==x) return x;
    return fa[x]=get_fa(fa[x]);
}
int rot[MAXN],tot;
int tre[MAXM],sl[MAXM],sr[MAXM];
void change(int &x, int l, int r, int pos){
    if(x==0) x=++tot;
    tre[x]+=1;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) change(sl[x], l, mid, pos);
    else change(sr[x], mid+1, r, pos);
}
int query(int x, int l, int r, int k){
    if(x==0||tre[x]<k) return 0;
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(tre[sl[x]]>=k) return query(sl[x], l, mid, k);
    else return query(sr[x], mid+1, r, k-tre[sl[x]]);
}
int merge(int a, int b, int l, int r){
    if(a==0||b==0) return a+b;
    if(l==r){
        tre[a]+=tre[b];
        return a;
    }
    int mid=(l+r)>>1;
    sl[a]=merge(sl[a], sl[b], l, mid);
    sr[a]=merge(sr[a], sr[b], mid+1, r);
    tre[a]=tre[sl[a]]+tre[sr[a]];
    return a;
}
int rank[MAXN],ref_rank[MAXN];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i) fa[i]=i;
    for(int i=1;i<=n;++i){
        rank[i]=read(),ref_rank[rank[i]]=i;
        change(rot[i], 1, n, rank[i]);
    }
    for(int i=1;i<=m;++i){
        int a=read(),b=read();
        int fa_a=get_fa(a),fa_b=get_fa(b);
        if(fa_a==fa_b) continue;
        fa[fa_b]=fa_a;
        rot[fa_a]=merge(rot[fa_a], rot[fa_b], 1, n);
    }
    int q=read();
    while(q--){
        char opt;
        scanf("
%c
", &opt);
        int a=read(),b=read();
        if(opt=='Q'){
            int ans=query(rot[get_fa(a)], 1, n, b);
            if(ans!=0) printf("%d
", ref_rank[ans]);
            else puts("-1");
        }else if(opt=='B'){
            int fa_a=get_fa(a),fa_b=get_fa(b);
            if(fa_a==fa_b) continue;
            fa[fa_b]=fa_a;
            rot[fa_a]=merge(rot[fa_a], rot[fa_b], 1, n);
        }else puts("erro");
    }
    return 0;
}