树形数据结构（二）

splay

splay 的基本原理

一般情况下，splay每操作一个节点，需要将该节点旋转至树根
在旋转的时候维护树的平衡性

splay 旋转和 splay 函数
splay 的旋转，需要维护二叉树的中序遍历的一致性

splay 维护信息

模版题

const int maxn = 1e5 + 10;
int n, m;

namespace Splay {
    class node {
    public:
        int son[2], pa;
        int sz, tag, v;

        node() = default;
        void init(int _v, int _pa) {
            v = _v, pa = _pa;
            sz = 1;
        }
    };

    int root = 0;
    int idx = 0;
    vector<node> t(maxn, node());

    inline void pull(int p) {
        t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;
    }

    inline void push(int p) {
        if (!t[p].tag) return;
        swap(t[p].son[0], t[p].son[1]);
        t[t[p].son[0]].tag ^= 1, t[t[p].son[1]].tag ^= 1;
        t[p].tag = 0;
    }
    void rotate(int x) {
        int y = t[x].pa, z = t[y].pa;
        int k = t[y].son[1] == x;

        t[z].son[t[z].son[1] == y] = x, t[x].pa = z;
        t[y].son[k] = t[x].son[k^1], t[t[x].son[k^1]].pa = y;
        t[x].son[k^1] = y, t[y].pa = x;
        pull(y), pull(x);
    }

    void splay(int x, int k) {
        while (t[x].pa != k) {
            int y = t[x].pa, z = t[y].pa;
            if (z != k) {
                if ((t[z].son[1] == y) ^ (t[y].son[1] == x)) rotate(x);
                else rotate(y);
            }
            rotate(x);
        }
        if (!k) root = x;
    }

    void insert(int val) {
        int u = root, p = 0;
        while (u) p = u, u = t[u].son[val > t[u].v];
        u = ++idx;
        if (p) t[p].son[val > t[p].v] = u;
        t[u].init(val, p);

        splay(u, 0);
    }

    int get_k(int k) {
        int u = root;
        while (u) {
            push(u);
            if (t[t[u].son[0]].sz >= k) u = t[u].son[0];
            else if (t[t[u].son[0]].sz + 1 == k) return u;
            else k -= t[t[u].son[0]].sz + 1, u = t[u].son[1];
        }
        return -1;
    }

    void print(int u) {
        push(u);
        if (t[u].son[0]) print(t[u].son[0]);
        if (t[u].v >= 1 && t[u].v <= n) printf("%d ", t[u].v);
        if (t[u].son[1]) print(t[u].son[1]);
    }
}

using namespace Splay;

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &m);

    for (int i = 0; i <= n+1; i++) insert(i);
    while (m--) {
        int li, ri;
        scanf("%d%d", &li, &ri);
        int l = get_k(li), r = get_k(ri+2);
        splay(l, 0), splay(r, l);
        t[t[r].son[0]].tag ^= 1;
    }
    print(root);
}

splay 维护信息

郁闷的出纳员

• 操作中涉及到将所有员工的工资都增加，容易想到用一个全局变量 $\Delta$ 来维护
  $\text{splay}$ 中维护的值为 $x$，那么员工真实的工资数值为 $x + \Delta$
• 招员工和员工离职，就是 $\text{splay}$ 中常见的添加，删除操作
• 比较难处理的是员工离职的情况，员工工资 $x + \Delta < \min$ 最低工资标准会离职
  • 在 splay 两端加入两个哨兵，$-\infty, \ +\infty$，splay 执行删除区间操作
    待删区间的左端点就是 $L = -\infty$，右端点是第一个满足 $t_R.v \geqslant \min-\Delta$ 的 $R$
    删除 $[L, R]$ 区间，将 $R$ splay 到根，并且将 $L$ splay 成 $R$ 的儿子，删除 $R$ 右子树即可
  • 找到 $\geqslant \min - \Delta$ 的最小数，实际上就是执行平衡二叉树的二分查找
    如果根节点 $u$ 满足， $u$ 是备选答案，接着去 $u$ 的左子树尝试找更小的

BST 找前驱和后继

splay 也是一种特殊的平衡二叉树，涉及找 $u$ 的前驱和后继问题
这和一般的平衡二叉树找前驱后继大同小异

前驱

void get_pre(int val) {
    int res = 0;
    // t[res].dat = -inf

    int u = root;
    while (u) {
        if (val == t[u].val) {
            if (t[u].son[0]) {
                u = t[u].son[0];
                while (t[u].son[1]) u = t[u].son[1];
                res = u;
            }
            break;
        }
        if (t[p].dat < val && t[p].dat > t[res].val) res = p;
        p = t[p].son[val >= t[p].val];
    }
    return t[res].val;
}

后继

void get_nxt(int val) {
    int res = 2;
    // t[2].dat = inf;
    
    int u = root;
    while (u) {
        if (t[u].val == val) {
            if (t[u].son[1]) {
                u = t[u].son[1];
                while (t[u].son[0]) u = t[u].son[0];
                res = u;
            }
            break;
        }
        if (t[u].dat > val && t[u].dat < t[res].dat) res = u;
        u = t[u].son[val >= t[u].dat];
    }
    return t[res].dat;
}

splay 启发式合并

永无乡

可以考虑用并查集维护连通性，同时完成启发式合并

1. 一开始先建 $n$ 棵 splay 树，对于连通的岛屿 $(a, b)$
   执行启发式合并，将较小的集合合并到较大的集合中，比如 $\textbf{size}(a) < \textbf{size}(b), \ a \to b$
2. 合并 $a \to b$，需要 $\textbf{dfs}(\text{root}(a))$，遍历 $a$ 子树的每一个点 $u$
   并且依次将 $u$ 插入 $b$ 这棵 splay 中
3. 查询第 $x$ 棵 splay 的第 $k$ 大树即可