[HNOI2012]永无乡

· · 题解

首先解释为什么要为一个有25篇题解的题目写题解

1.可以看到，题解区绝大多数dalao选择了指针，而想必很多选手（包括我这个juruo）更习惯于用数组维护。

所以这里给出一种让空间不爆炸的数组实现方法！

2.为什么没有Treap的题解啊，一定要有一篇！

题目链接

下面开始讲这道题。

题目中只要求我们维护岛屿的连通性，可以考虑用并查集维护，一开始所有岛屿是孤立的，每次B操作就将两个连通块连接起来，每次Q操作查询fa[x]的岛屿连接的第k重要的岛屿是那一座。

显然，我们需要用到启发式合并，即把小的连通块插入到大的连通块中。感性理解，如果反过来做，肯定是不优的。合并只需暴力合并即可满足时间需求。

那为什么题解区指针居多呢？大概是因为空间无法满足吧。

其实我们只要在删除了某个节点后，在将它插入到一个新的树的时候，继续使用那个下标即可。

然后就是普通的Treap模板了。

#include<bits/stdc++.h>
using namespace std;
#define reg register
#define chk_digit(c) (c>='0'&&c<='9')
inline int read() {
    reg int x=0,f=1;reg char c=getchar();
    while(!chk_digit(c)) { if(c=='-') f=-1;c=getchar(); }
    while(chk_digit(c)) x=x*10+c-'0',c=getchar();
    return x*f;
} 
inline char get_char() {
    reg char c=getchar();
    while(c!='B'&&c!='Q') c=getchar();
    return c;
} 
#define maxsize 2000000
#define MAXN 100005
#define inf 2000000000
struct treap{ int l,r,rand_num,times,size,val; }tr[maxsize];
int tot,root[MAXN],num[MAXN],id[MAXN],n,m,fa[MAXN],s[MAXN],q;
inline int New(int val) { tr[++tot].val=val,tr[tot].rand_num=rand(),tr[tot].size=tr[tot].times=1;return tot; }
inline void update(int p) { tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].times; }
inline void build(int bel) { int now=tot+1;New(-inf),New(inf),root[bel]=now,tr[now].r=now+1,update(root[bel]); }
inline int get_val(int p,int rank) {
    if(!p) return inf;
    if(tr[tr[p].l].size>=rank) return get_val(tr[p].l,rank);
    if(tr[tr[p].l].size+tr[p].times>=rank) return tr[p].val;
    return get_val(tr[p].r,rank-tr[p].times-tr[tr[p].l].size);
}
inline void zig(int &p) { int q=tr[p].l;tr[p].l=tr[q].r,tr[q].r=p,p=q,update(tr[p].r),update(p); }
inline void zag(int &p) { int q=tr[p].r;tr[p].r=tr[q].l,tr[q].l=p,p=q,update(tr[p].l),update(p); }
inline void insert(int &p,int val) {
    if(!p) { p=New(val);return; }
    if(val==tr[p].val) { ++tr[p].times,update(p);return; }
    if(val<tr[p].val) {
        insert(tr[p].l,val);
        if(tr[p].rand_num<tr[tr[p].l].rand_num) zig(p);
    }
    else {
        insert(tr[p].r,val);
        if(tr[p].rand_num<tr[tr[p].r].rand_num) zag(p); 
    }
    update(p);
}
inline void renew(int p) { tr[p].size=tr[p].times=1,tr[p].l=tr[p].r=0; }//插入之前先把原先的信息除去
inline void add(int &p,int val,int where) {//这段代码有一点冗余了，但是它却能够进行内存的循环利用
    if(!p) { p=where;return; } 
    if(val<tr[p].val) {
        add(tr[p].l,val,where);
        if(tr[p].rand_num<tr[tr[p].l].rand_num) zig(p);
    }
    else {
        add(tr[p].r,val,where);
        if(tr[p].rand_num<tr[tr[p].r].rand_num) zag(p);
    }
    update(p);
}
inline void dfs(int p,int bel) {//对要被合并进大的连通块的小连通块dfs，并把它插入大的连通块中
    if(tr[p].l) dfs(tr[p].l,bel);
    if(tr[p].r) dfs(tr[p].r,bel);
    if(tr[p].val!=inf&&tr[p].val!=-inf)
    renew(p),add(root[bel],tr[p].val,p);
}
inline int szfind(int x) { return x==fa[x]?x:fa[x]=szfind(fa[x]); }
inline int szunion(int x,int y) { fa[y]=x,s[x]+=s[y]; } /并查集模板
int main() {
    n=read(),m=read(),srand(time(0)),id[0]=-1;
    for(reg int i=1;i<=n;++i) {
        int x=read();
        num[i]=x,id[x]=i,fa[i]=i,build(i),s[i]=1,insert(root[i],x);
    }
    for(reg int i=1;i<=m;++i) {
        int x=read(),y=read();
        if(szfind(x)==szfind(y)) continue;
        if(s[fa[x]]<s[fa[y]]) x^=y,y^=x,x^=y;
        dfs(root[fa[y]],fa[x]),szunion(fa[x],fa[y]);
    }
    q=read();
    for(reg int i=1;i<=q;++i) {
        char opt=get_char();int x=read(),y=read();
        if(opt=='Q') {
            int z=get_val(root[szfind(x)],y+1);
            if(z==inf||z==0) printf("-1\n");
            else printf("%d\n",id[z]);
        }
        if(opt=='B') {
            if(szfind(x)==szfind(y)) continue;
            if(s[fa[x]]<s[fa[y]]) x^=y,y^=x,x^=y;//启发式合并
            dfs(root[fa[y]],fa[x]),szunion(fa[x],fa[y]);
        }
    }
}

当然，insert还可以改成这样写，相对简洁

inline void insert(int &p,int val,int rem=0) {
    if(!p) { rem?p=rem,tr[rem].val=val,tr[rem].l=tr[rem].r=0:p=New(val);return; }
    if(val==tr[p].val) { ++tr[p].times,update(p);return; }
    if(val<tr[p].val) {
        insert(tr[p].l,val,rem);
        if(tr[p].rand_num<tr[tr[p].l].rand_num) zig(p); 
    }
    else {
        insert(tr[p].r,val,rem);
        if(tr[p].rand_num<tr[tr[p].r].rand_num) zag(p);
    }
    update(p);
}