题解 P3224 【[HNOI2012]永无乡】

2017-09-25 18:22:27


用线段树启发式合并代替平衡树很方便啊

而且还好写

#include<bits/stdc++.h>
using namespace std;
int n,m,kk,a[1000000],f[1000000],q,x,y,sum[5000000],ff[5000000],l[5000000],r[5000000];
char c;
int fa(int x){return f[x]==x?x:f[x]=fa(f[x]);}//奇怪的并查集维护
void putit(int d,int x,int y,int ll,int rr){//加入一个元素
    if (ll==rr){sum[d]++;ff[d]=y;return;}
    int m=(ll+rr)/2;
    if (x<=m){
        if (!l[d])l[d]=++kk;
        putit(l[d],x,y,ll,m);
    }else{
        if (!r[d])r[d]=++kk;
        putit(r[d],x,y,m+1,rr);
    }sum[d]=sum[l[d]]+sum[r[d]];
    if (r[d])ff[d]=ff[r[d]];else ff[d]=ff[l[d]];
}int hb(int x,int y){//合并两个元素
    if (x==y)return x;
    if (x==0)return y;if (y==0)return x;
    sum[x]+=sum[y];l[x]=hb(l[x],l[y]);r[x]=hb(r[x],r[y]);
    if (r[x])ff[x]=ff[r[x]];else ff[x]=ff[l[x]];
    return x;
}int findit(int x,int y){//寻找一个集合内第y大的元素
    if (y>sum[x])return -1;
    if (y==sum[x])return ff[x];
    if (y>sum[l[x]])return findit(r[x],y-sum[l[x]]);
        else return findit(l[x],y);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;kk=n;
    for (int i=1;i<=n;i++)cin>>a[i],f[i]=i,putit(i,a[i],i,1,n);
    for (int i=1;i<=m;i++)cin>>x>>y,x=fa(x),y=fa(y),f[y]=f[x]=hb(x,y);
    cin>>q;while (q--){
        cin>>c>>x>>y;
        if (c=='Q')cout<<findit(fa(x),y)<<endl;
            else x=fa(x),y=fa(y),f[y]=f[x]=hb(x,y);
    }
}