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

ajcxsu
ajcxsu 2018年01月18日
  • 62 次阅读

今天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;
}

本文链接:https://acxblog.site/archives/sol_luogu_3224.html
本文采用 CC BY-NC-SA 3.0 协议进行许可