[题解 && Splay启发式合并] Luogu P3224 [HNOI2012] 永无乡

Author Avatar
空気浮遊 2018年01月18日
  • 在其它设备中阅读本文章

今天 A 了两道平衡树感觉自己圆满了...

Konachan.com - 257572 boat brown_eyes brown_hair idolmaster idolmaster_cinderella_girls kusano_shinta long_hair ponytail skirt tachibana_arisu water.jpg

Problem

永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连通的。

现在有两种操作:

B x y 表示在岛 x 与岛 y 之间修建一座新桥。

Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座,请你输出那个岛的编号。

Solution

本题教会我们使用 Splay 启发式合并。
啥是启发式合并呢?把小的那个 splay 一个个合并到大的那个叫启发式合并。
像我这种懒的就直接去新建一个个点 insert 到那个大的就没了。

额外的话,这次使用的是没有维护父指针的 Splay,又有所心得。
递归版 Splay 最重要的地方在于维护根节点指针,也就是说 如果根节点指针可能被更改,必须全程维持引用状态 。否则 gg。
自己稍微注意了一下,否则可能又会陷入无限 debug 的深渊当中。

现在还无法总结出到底什么时候下该使用非递归还是递归版的 splay。嘛递归版的 splay 确实写起来简单一点,但引用是相当重要的一点,随时可能 gg。
非递归版的 splay 辣鸡又长...
哎反正两个差不多吧 233

然后还有一些细节处理。比如启发式合并引用不能 swap 等(引用下 swap 是个挺微妙的事情,还是要多加注意),然后哪个合并到哪个决定了并查集的合并。再强调:每个点的根节点都必须好好维护,也就是引用的问题。或者你可以放弃递归版本 splay。

你问这题怎么做?不是告诉过你了吗 \_(:зゝ∠)\_
维护 splay,启发式合并不就行了 w

Code

// Code by ajcxsu
// Problem: P3224

#include<bits/stdc++.h>
#define INF (0x3f3f3f3f)
using namespace std;

const int N=1e5+10;
int va[N],id[N];
int n,m,q;

/* Splay */
struct Node *nil;
struct Node {
    int v,s,c;
    Node *ch[2];
    Node (int v=0): v(v),s(1),c(1) { ch[0]=ch[1]=nil; }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
    int cmp(int val) {
        if(val==v) return -1;
        else return val>v;
    }
} *pos[N];
void init() {
    nil=new Node(-INF);
    nil->ch[0]=nil->ch[1]=nil;
    nil->s=nil->c=0;
}
void rot(Node *&x, bool type) {
    Node *t=x->ch[type];
    x->ch[type]=t->ch[!type];
    t->ch[!type]=x;
    x->upd(), t->upd();
    x=t;
}
void splay(Node *&x, int val) { // 引用重要,省去更改父节点儿子的步骤
    int d=x->cmp(val);
    if(d!=-1 && x->ch[d]!=nil) {
        Node *&y=x->ch[d];
        int d2=y->cmp(val);
        if(d2!=-1 && y->ch[d2]!=nil) {
            splay(y->ch[d2], val);
            if(d==d2) rot(x,d),rot(x,d);
            else rot(y,d2), rot(x,d);
        }
        else rot(x,d);
    }
}

Node *split(Node *&x, int val) {
    Node *x1,*x2;
    splay(x, val);
    if(x->v<=val) x1=x, x2=x->ch[1], x->ch[1]=nil;
    else x1=x->ch[0], x2=x, x->ch[0]=nil;
    x->upd();
    x=x1;
    return x2;
}

void merge(Node *&x1, Node *&x2) {
    if(x1==nil) swap(x1,x2);
    splay(x1,INF);
    x1->ch[1]=x2, x1->upd();
    x2=nil;
}

void ins(int val, Node *&root) {
    Node *x2=split(root, val);
    Node *nd=new Node(val);
    merge(root, nd);
    merge(root, x2);
}

int kth(Node *x, int k) {
    int ss=x->ch[0]->s;
    if(k<=ss) return kth(x->ch[0],k);
    else if(k<=ss+x->c) return id[x->v];
    else return kth(x->ch[1],k-ss-x->c);
}

void dfs(Node *x) {
    if(x==nil) return;
    dfs(x->ch[0]), printf("%d ",x->v), dfs(x->ch[1]);
} // 调试函数

int Find(int); // 函数声明
int rank(int x,int k) {
    int xf=Find(x);
    if(k<1 || k>pos[xf]->s) return -1;
    return kth(pos[xf], k);
}

// 启发式合并
namespace smerge{
    void dfs(Node *x,Node *&root) { // 引用很重要...
        if(x==nil) return;
        dfs(x->ch[0], root), dfs(x->ch[1], root);
        ins(x->v, root);
        delete x;
    }
    bool main(Node *&a, Node *&b) {
        bool ret=0;
        if(a->s > b->s) dfs(b,a), ret=1;
        else dfs(a,b);
        return ret;
    }
}

/* 并查集 */
int fa[N];
int Find(int x) {
    if(!fa[x]) return x;
    return fa[x]=Find(fa[x]);
}
void Union(int a,int b) {
    int af=Find(a), bf=Find(b);
    if(af==bf) return;
    if(smerge::main(pos[af],pos[bf])) fa[bf]=af;
    else fa[af]=bf;
}

void gn(int &x) {
    x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar();
}
char gb() {
    char ch=getchar();
    while(ch<'A' || ch>'Z') ch=getchar();
    return ch;
}

int main() {
    init();
    gn(n), gn(m);
    for(int i=1;i<=n;i++) {
        gn(va[i]), id[va[i]]=i;
        pos[i]=new Node(va[i]);
    }
    int u,v;
    for(int i=1;i<=m;i++) {
        gn(u), gn(v);
        Union(u,v);
    }
    gn(q);
    char opt;
    while(q--) {
        opt=gb(), gn(u), gn(v);
        if(opt=='B') Union(u,v);
        else printf("%d\n",rank(u,v));
    }
    return 0;
}