题解 P3224 【[HNOI2012]永无乡】

· · 题解

主要是自己mark一波骗分算法，建议追求极致的同学还是不要看了，但是联赛前还是要看一波的防止数据结构调不出来gg的情况，毕竟用STL过数据结构题不需要智商

这道题是并查集启发式合并＋平衡树

其实也可以用vector+upper_bound来模拟set的操作

我们用平衡树来实现非区间操作的时候其实是通过排序树的结构来保持元素的有序性

因此我们也可以直接模拟这个数组来使元素变得有序＾－＾

vector 　

不仅可以支持STL的二分查找(lower_bound(),upper_bound())

还可以支持想链表一样的中间插入

还可以直接像数组一样访问元素

还是分配的动态内存

在合并完之后还可以直接销毁，释放内存

所以就是它了！！！

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int rk[100002],n,m,fa[100002],op[100002];
int getfa(int k){if(fa[k]==k) return k;return fa[k]=getfa(fa[k]);}
inline int read(){int x=0,y=1;char k;while(k<'0'||k>'9'){if(k=='-')y=-1;k=getchar();}while(k>='0'&&k<='9'){x=(x<<3)+(x<<1)+k-'0';k=getchar();}return x*y;}
vector<int>c[100001];
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) rk[i]=read(),fa[i]=i,op[rk[i]]=i;
    for(int i=1;i<=m;i++){
        int a=read(),b=read();
        int f1=getfa(a),f2=getfa(b);
        fa[f2]=f1;
    }for(int i=1;i<=n;i++){int f=getfa(i);c[f].insert(upper_bound(c[f].begin(),c[f].end(),rk[i]),rk[i]);}
    int T=read();
    while(T--){
        char con[10];scanf("%s",con);
        int a=read(),b=read();
        if(con[0]=='Q'){
            int f=getfa(a);
            if((unsigned int)b>c[f].size()){printf("-1\n");continue;}            
            printf("%d\n",op[c[f][b-1]]);
        }else{
            int f1=getfa(a),f2=getfa(b);
            if(c[f1].size()<c[f2].size()){swap(f1,f2);swap(a,b);}
            for(vector<int>::iterator it=c[f2].begin();it!=c[f2].end();it++){
                int t=*it;
                c[f1].insert(upper_bound(c[f1].begin(),c[f1].end(),t),t);
            }vector<int>().swap(c[f2]);
            fa[f2]=f1;
        }
    }
    return 0;
}