平衡树学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-02-01 21:04

点击数:238

其实是学过的,然后,就忘了……
本文介绍 Splay/Link Cut Tree/FHQ Treap 三种平衡树相关的数据结构。

Contents hide

Splay

Splay 是一种二叉查找树,它通过不断将某个节点旋转到根节点,使得整棵树仍然满足二叉查找树的性质,并且保持平衡而不至于退化为链。

变量信息

$rt$ $tot$ $f_p$ $ch_{p,0/1}$ $a_p$ $c_p$ $s_p$
根节点 节点个数 父节点 左/右儿子 节点权值 权值次数 子树大小
struct Splay {
    int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
};

维护操作

$\operatorname{upd}(p)$

更新 $s_p$。

    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]

$\operatorname{get}(p)$

判断 $p$ 是 $f_p$ 的左儿子还是右儿子。

    #define get(p) (p == ch[f[p]][1])

$\operatorname{clr}(p)$

销毁 $p$。

    #define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0

$\operatorname{rot}(p)$

将 $p$ 旋转上移一个位置。

    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y)) ch[y][v] = p;
    }

$\operatorname{splay}(p, g)$

这是 splay 中最重要的操作。

将 $p$ 旋转为 $g$ 的儿子(若 $g$ 为 $0$ 则旋转为根)。

    inline void splay(int p, int g = 0) {
        for (int x = f[p]; (x = f[p]) != g; rot(p))
            if (f[x] != g) rot(get(p) == get(x) ? x : p);
        if (!g) rt = p;
    }

访问操作

$\operatorname{ins}(k)$

插入 $k$。

    inline void ins(int k) {
        if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
        int x = rt, y = 0;
        while (1) {
            if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
            y = x, x = ch[x][a[x]<k];
            if (!x) {
                a[++tot] = k, c[tot] = s[tot] = 1;
                f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
                return splay(tot);
            }
        }
    }

$\operatorname{rnk}(k)$

查询 $k$ 的排名($<k$ 的数的个数 $+1$)。

    inline int rnk(int k) {
        int p = rt, x = 0;
        while (1)
            if (k < a[p]) {
                if (!lc) return splay(p), x + 1;
                p = lc;
            } else {
                x += s[lc];
                if (k == a[p]) return splay(p), x + 1;
                x += c[p];
                if (!rc) return splay(p), x + 1;
                p = rc;
            }
    }

$\operatorname{kth}(k)$

查询排名为 $k$ 的数。

    inline int kth(int k) {
        int p = rt;
        while (1)
            if (k <= s[lc]) p = lc;
            else {
                k -= s[lc];
                if (k <= c[p]) return splay(p), a[p];
                k -= c[p], p = rc;
            }
    }

$\operatorname{pre}(k)$

查询 $k$ 的前驱($<k$ 的最大的数)。

    inline int pre(int k) {
        return kth(rnk(k) - 1);
    }

$\operatorname{nxt}(k)$

查询 $k$ 的后继($>k$ 的最小的数)。

    inline int nxt(int k) {
        return kth(rnk(k + 1));
    }

$\operatorname{del}(k)$

删除 $k$(如果没有则跳过)。

    inline void del(int k) {
        rnk(k);
        if (k != a[rt]) return;
        if (c[rt] > 1) return --c[rt], --s[rt], void();
        int p = rt;
        if (!lc && !rc) return rt = 0, clr(p), void();
        if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
        return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
    }

【模板】P3369 【模板】普通平衡树

const int N = 1e5 + 7;

struct Splay {
    int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
    #define get(p) (p == ch[f[p]][1])
    #define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y)) ch[y][v] = p;
    }
    inline void splay(int p, int g = 0) {
        for (int x = f[p]; (x = f[p]) != g; rot(p))
            if (f[x] != g) rot(get(p) == get(x) ? x : p);
        if (!g) rt = p;
    }
    inline void ins(int k) {
        if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
        int x = rt, y = 0;
        while (1) {
            if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
            y = x, x = ch[x][a[x]<k];
            if (!x) {
                a[++tot] = k, c[tot] = s[tot] = 1;
                f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
                return splay(tot);
            }
        }
    }
    inline int rnk(int k) {
        int p = rt, x = 0;
        while (1)
            if (k < a[p]) {
                if (!lc) return splay(p), x + 1;
                p = lc;
            } else {
                x += s[lc];
                if (k == a[p]) return splay(p), x + 1;
                x += c[p];
                if (!rc) return splay(p), x + 1;
                p = rc;
            }
    }
    inline int kth(int k) {
        int p = rt;
        while (1)
            if (k <= s[lc]) p = lc;
            else {
                k -= s[lc];
                if (k <= c[p]) return splay(p), a[p];
                k -= c[p], p = rc;
            }
    }
    inline int pre(int k) {
        return kth(rnk(k) - 1);
    }
    inline int nxt(int k) {
        return kth(rnk(k + 1));
    }
    inline void del(int k) {
        rnk(k);
        if (k != a[rt]) return;
        if (c[rt] > 1) return --c[rt], --s[rt], void();
        int p = rt;
        if (!lc && !rc) return rt = 0, clr(p), void();
        if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
        return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
    }
} splay;

int main() {
    int n;
    rd(n);
    for (int i = 1, o, x; i <= n; i++) {
        rd(o), rd(x);
        switch (o) {
            case 1 : splay.ins(x); break;
            case 2 : splay.del(x); break;
            case 3 : print(splay.rnk(x)); break;
            case 4 : print(splay.kth(x)); break;
            case 5 : print(splay.pre(x)); break;
            case 6 : print(splay.nxt(x)); break;
        }
    }
    return 0;
}

【模板】P3391 【模板】文艺平衡树

const int N = 1e5 + 7;
int n, m;

struct Splay {
    int rt, tot, f[N], ch[N][2], a[N], c[N], s[N], v[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
    #define get(p) (p == ch[f[p]][1])
    #define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    inline void spd(int p) {
        if (p && v[p]) {
            if (lc) rev(lc);
            if (rc) rev(rc);
            v[p] = 0;
        }
    }
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y)) ch[y][v] = p;
    }
    inline void splay(int p, int g = 0) {
        for (int x = f[p]; (x = f[p]) != g; rot(p))
            if (f[x] != g) rot(get(p) == get(x) ? x : p);
        if (!g) rt = p;
    }
    inline void ins(int k) {
        if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
        int x = rt, y = 0;
        while (1) {
            if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
            y = x, x = ch[x][a[x]<k];
            if (!x) {
                a[++tot] = k, c[tot] = s[tot] = 1;
                f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
                return splay(tot);
            }
        }
    }
    inline int kth(int k) {
        int p = rt;
        while (1) {
            spd(p);
            if (k <= s[lc]) p = lc;
            else {
                k -= s[lc];
                if (k <= c[p]) return splay(p), p;
                k -= c[p], p = rc;
            }
        }
    }
    inline void work(int l, int r) {
        l = kth(l - 1), r = kth(r + 1), splay(l), splay(r, l), rev(ch[r][0]);
    }
    void dfs(int p) {
        spd(p);
        if (lc) dfs(lc);
        if (a[p] && a[p] <= n) print(a[p], ' ');
        if (rc) dfs(rc);
    }
} splay;

int main() {
    rd(n), rd(m);
    for (int i = 0; i <= n + 1; i++) splay.ins(i);
    for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), splay.work(l + 1, r + 1);
    splay.dfs(splay.rt);
    return 0;
}

Link Cut Tree

Link Cut Tree (LCT) 是一种数据结构,我们用它来解决动态树问题。Splay 是 LCT 的基础,但是 LCT ⽤的 Splay 和普通的 Splay 在细节处不太一样(进行了一些扩展)。

LCT 的主要结构

LCT 由多个 Splay 构成,维护一个树,树的每个节点与所有 Splay 节点一一对应。

树的每条边分为实边虚边

对于实边,每一个 Splay 通过其中序遍历维护一条从上到下在原树中的深度严格递增的实链

对于虚边,各个 Splay 之间并不是独立的。每个 Splay 的根节点的父亲节点本应是空,但在 LCT 中每个 Splay 的根节点的父亲节点指向原树中这条实链的最顶端的点的父亲节点。每个这样的指向对应了原树中的一条虚边,其特点在于认父不认子。因此,每个连通块恰好有一个点的父亲节点为空。

变量信息

$f_p$ $ch_{p,0/1}$ $s_p$ $v_p$ $a_p$ $c_p$
父节点 左/右儿子 子树大小 翻转标记 节点权值 路径权值异或和
struct LCT {
    int f[N], ch[N][2], s[N], v[N], a[N], c[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
};

维护操作

$\operatorname{upd}(p)$

更新 $s_p$ 和 $c_p$。

    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]

$\operatorname{get}(p)$

判断 $p$ 是 $f_p$ 的左儿子还是右儿子。

    #define get(p) (p == ch[f[p]][1])

$\operatorname{rev}(p)$

翻转 $p$。

    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])

$\operatorname{isrt}(p)$

判断 $p$ 是否为所在 Splay 的根

    #define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)

$\operatorname{spd}(p)$

下传 $v_p$。

    inline void spd(int p) {
        if (p && v[p]) {
            if (lc) rev(lc);
            if (rc) rev(rc);
            v[p] = 0;
        }
    }

$\operatorname{rot}(p)$

将 $p$ 旋转上移一个位置。

    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y) && !o) ch[y][v] = p;
    }

$\operatorname{pre}(p)$

$\operatorname{splay}(p)$ 之前的准备工作,要把路径上的点都 $\operatorname{spd}(p)$ 一下。

    void pre(int p) {
        if (!isrt(p)) pre(f[p]);
        spd(p);
    }

$\operatorname{splay}(p)$

将 $p$ 旋转为所在 Splay 的根

    inline void splay(int p) {
        pre(p);
        for (int x = f[p]; !isrt(p); rot(p), x = f[p])
            if (!isrt(x)) rot(get(p) == get(x) ? x : p);
    }

$\operatorname{access}(p)$

这是 LCT 中最重要的操作。

把从原树的根到 $p$ 的路径拉成一条实链放到一个 Splay 里。

    inline void access(int p) {
        for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
    }

$\operatorname{mkrt}(p)$

使 $p$ 直接成为原树的根

    inline void mkrt(int p) {
        access(p), splay(p), rev(p);
    }

$\operatorname{split}(x, y)$

把原树中 $x,y$ 之间的路径拉成一条实链放到一个 Splay 里(同时使 $y$ 成为原树的根)。

    inline void split(int x, int y) {
        mkrt(x), access(y), splay(y);
    }

访问操作

$\operatorname{fdrt}(p)$

找到 $p$ 所在的原树的根

    inline int fdrt(int p) {
        access(p), splay(p);
        while (lc) spd(p), p = lc;
        return splay(p), p;
    }

$\operatorname{link}(x, y)$

在原树的 $x,y$ 两点间连一条边(若已经连通则不连)。

    inline bool link(int x, int y) {
        mkrt(x);
        return fdrt(y) != x && (f[x] = y);
    }

$\operatorname{cut}(x, y)$

将原树的 $x,y$ 两点间的边删掉(若不存在则不删)。

    inline bool cut(int x, int y) {
        mkrt(x);
        if (fdrt(y) != x || s[x] != 2) return 0;
        return f[y] = ch[x][1] = 0, upd(x), 1;
    }

$\operatorname{chg}(p, x)$

将 $p$ 的点权修改为 $x$。

    inline void chg(int p, int x) {
        mkrt(p), a[p] = x, upd(p);
    }

【模板】P3690 【模板】Link Cut Tree (动态树)

const int N = 1e5 + 7;
int n, m;

struct LCT {
    int f[N], ch[N][2], s[N], v[N], a[N], c[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]
    #define get(p) (p == ch[f[p]][1])
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    #define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
    inline void spd(int p) {
        if (p && v[p]) {
            if (lc) rev(lc);
            if (rc) rev(rc);
            v[p] = 0;
        }
    }
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y) && !o) ch[y][v] = p;
    }
    void pre(int p) {
        if (!isrt(p)) pre(f[p]);
        spd(p);
    }
    inline void splay(int p) {
        pre(p);
        for (int x = f[p]; !isrt(p); rot(p), x = f[p])
            if (!isrt(x)) rot(get(p) == get(x) ? x : p);
    }
    inline void access(int p) {
        for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
    }
    inline void mkrt(int p) {
        access(p), splay(p), rev(p);
    }
    inline void split(int x, int y) {
        mkrt(x), access(y), splay(y);
    }
    inline int fdrt(int p) {
        access(p), splay(p);
        while (lc) spd(p), p = lc;
        return splay(p), p;
    }
    inline bool link(int x, int y) {
        mkrt(x);
        return fdrt(y) != x && (f[x] = y);
    }
    inline bool cut(int x, int y) {
        mkrt(x);
        if (fdrt(y) != x || s[x] != 2) return 0;
        return f[y] = ch[x][1] = 0, upd(x), 1;
    }
    inline void chg(int p, int x) {
        mkrt(p), a[p] = x, upd(p);
    }
} lct;

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) rd(lct.a[i]), lct.c[i] = lct.a[i], lct.s[i] = 1;
    for (int i = 1, o, x, y; i <= m; i++) {
        rd(o), rd(x), rd(y);
        switch (o) {
            case 0 : lct.split(x, y), print(lct.c[y]); break;
            case 1 : lct.link(x, y); break;
            case 2 : lct.cut(x, y); break;
            case 3 : lct.chg(x, y); break;
        }
    }
    return 0;
}

常见应用

  1. 维护链信息(平衡树操作)
  2. 动态维护连通性 & 边双联通分量(可以说是并查集的升级,因为并查集只能连不能断)
  3. 维护边权(将边当成点进行操作,常用于维护生成树)
  4. 维护子树信息

维护子树信息

有时候,我们需要的并不是维护链的信息,而是子树的信息。要知道,LCT 强于维护链的信息,而弱于维护子树的信息。然而动态的连边和断边,又不得不要求我们使用 LCT 来维护。

我们已经可以通过 Splay 来获知实子树(也就是原树中的一条链)的信息总和,现在只需要维护虚子树的信息总和,然后两者相加即可。

讨论一下 LCT 中的每个操作会对虚实边产生怎样的影响,结果你会惊奇的发现,只有 $\operatorname{access}(p)$ 和 $\operatorname{link}(p)$ 需要进行小小的修改就能轻松的维护了。

FHQ Treap

Treap 是一种弱平衡的二叉搜索树。Treap 这个单词是 Tree 和 Heap 的组合,表明 Treap 是一种由树和堆组合形成的数据结构。Treap 除了本身储存的值要满足二叉搜索树的性质之外,每个结点上要额外储存一个值,这个值需满足大根堆的性质。而这个额外的值是每个结点建立时随机生成的,因此 Treap 是期望平衡的。

Treap 分为旋转式和无旋式两种,FHQ Treap 即无旋式 Treap。FHQ Treap 的操作方式使得它天生支持维护序列、可持久化等特性,从而使这个东西严格意义上吊打无旋式 Treap 和 Splay,它们能搞的事情 FHQ Treap 都能搞。

变量信息及基本维护操作

$rt$ $tot$ $ch_{p,0/1}$ $a_p$ $d_p$ $s_p$
根节点 节点个数 左/右儿子 节点权值 节点随机值 子树大小
struct Treap {
    int rt, tot, ch[N][2], a[N], d[N], s[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
    #define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
} treap;

维护操作

FHQ Treap 的维护操作仅有两个,分裂 (split) 与合并 (merge)。

分裂 (split)

分裂过程接受两个参数:根指针 $p$ 和关键值 $k$。结果为将根指针指向的 Treap 分裂为两个 Treap,第一个 Treap 所有结点的关键值小于等于 $k$,第二个 Treap 所有结点的关键值大于 $k$。

    inline void split(int p, int k, int &x, int &y) {
        if (!p) return x = y = 0, void();
        if (a[p] <= k) x = p, split(rc, k, rc, y);
        else y = p, split(lc, k, x, lc);
        upd(p);
    }

合并 (merge)

合并过程接受两个参数:左 Treap 的根指针 $x$、右 Treap 的根指针 $y$,必须满足 $x$ 中所有结点的关键值小于等于 $y$ 中所有结点的关键值。因为两个 Treap 已经有序,我们只需要考虑额外的随机值来决定哪个 Treap 应与另一个 Treap 的儿子合并。

    inline int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
        return ch[x][1] = merge(ch[x][1], y), upd(x), x;
    }

访问操作

$\operatorname{ins}(k)$

插入 $k$。

    inline void ins(int k) {
        a[++tot] = k, s[tot] = 1, d[tot] = rand();
        if (!rt) return rt = tot, void();
        int x, y;
        split(rt, k, x, y), rt = merge(merge(x, tot), y);
    }

$\operatorname{rnk}(k)$

查询 $k$ 的排名($<k$ 的数的个数 $+1$)。

    inline int rnk(int k) {
        int x, y, ret;
        return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
    }

$\operatorname{kth}(k)$

查询排名为 $k$ 的数。

    inline int kth(int k) {
        int p = rt;
        while (1)
            if (k <= s[lc]) p = lc;
            else {
                k -= s[lc] + 1;
                if (!k) return a[p];
                p = rc;
            }
    }

$\operatorname{pre}(k)$

查询 $k$ 的前驱($<k$ 的最大的数)。

    inline int pre(int k) {
        return kth(rnk(k) - 1);
    }

$\operatorname{nxt}(k)$

查询 $k$ 的后继($>k$ 的最小的数)。

    inline int nxt(int k) {
        return kth(rnk(k + 1));
    }

$\operatorname{del}(k)$

删除 $k$(如果没有则跳过)。

    inline void del(int k) {
        int x, y, z;
        split(rt, k, x, z), split(x, k - 1, x, y);
        rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
        clr(y);
    }

【模板】P3369 【模板】普通平衡树

const int N = 1e5 + 7;

struct Treap {
    int rt, tot, ch[N][2], a[N], d[N], s[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
    #define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
    inline void split(int p, int k, int &x, int &y) {
        if (!p) return x = y = 0, void();
        if (a[p] <= k) x = p, split(rc, k, rc, y);
        else y = p, split(lc, k, x, lc);
        upd(p);
    }
    inline int merge(int x, int y) {
        if (!x || !y) return x | y;
        if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
        return ch[x][1] = merge(ch[x][1], y), upd(x), x;
    }
    inline void ins(int k) {
        a[++tot] = k, s[tot] = 1, d[tot] = rand();
        if (!rt) return rt = tot, void();
        int x, y;
        split(rt, k, x, y), rt = merge(merge(x, tot), y);
    }
    inline int rnk(int k) {
        int x, y, ret;
        return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
    }
    inline int kth(int k) {
        int p = rt;
        while (1)
            if (k <= s[lc]) p = lc;
            else {
                k -= s[lc] + 1;
                if (!k) return a[p];
                p = rc;
            }
    }
    inline int pre(int k) {
        return kth(rnk(k) - 1);
    }
    inline int nxt(int k) {
        return kth(rnk(k + 1));
    }
    inline void del(int k) {
        int x, y, z;
        split(rt, k, x, z), split(x, k - 1, x, y);
        rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
        clr(y);
    }
} treap;

int main() {
    int n;
    rd(n), treap.ins(-1e9), treap.ins(1e9); 
    for (int i = 1, o, x; i <= n; i++) {
        rd(o), rd(x);
        switch (o) {
            case 1 : treap.ins(x); break;
            case 2 : treap.del(x); break;
            case 3 : print(treap.rnk(x) - 1); break;
            case 4 : print(treap.kth(x + 1)); break;
            case 5 : print(treap.pre(x)); break;
            case 6 : print(treap.nxt(x)); break;
        }
    }
    return 0;
}

【模板】P3391 【模板】文艺平衡树

const int N = 1e5 + 7;
int n, m;

struct Treap {
    int rt, tot, ch[N][2], a[N], d[N], s[N], v[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    inline void spd(int p) {
        if (p && v[p]) {
            if (lc) rev(lc);
            if (rc) rev(rc);
            v[p] = 0;
        }
    }
    inline void split(int p, int k, int &x, int &y) {
        if (!p) return x = y = 0, void();
        spd(p);
        if (s[lc] < k) x = p, k -= s[lc] + 1, split(rc, k, rc, y);
        else y = p, split(lc, k, x, lc);
        upd(p);
    }
    inline int merge(int x, int y) {
        if (!x || !y) return x | y;
        spd(x), spd(y);
        if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
        return ch[x][1] = merge(ch[x][1], y), upd(x), x;
    }
    inline void ins(int k) {
        a[++tot] = k, s[tot] = 1, d[tot] = rand();
        if (!rt) return rt = tot, void();
        int x, y;
        split(rt, k, x, y), rt = merge(merge(x, tot), y);
    }
    inline void work(int l, int r) {
        int x, y, z;
        split(rt, r, x, z), split(x, l - 1, x, y);
        rev(y), merge(merge(x, y), z);
    }
    void dfs(int p) {
        spd(p);
        if (lc) dfs(lc);
        if (a[p] && a[p] <= n) print(a[p], ' ');
        if (rc) dfs(rc);
    }
} treap;

int main() {
    rd(n), rd(m);
    for (int i = 0; i <= n + 1; i++) treap.ins(i);
    for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), treap.work(l + 1, r + 1);
    treap.dfs(treap.rt);
    return 0;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注