splay模板

constexpr int N = 100005;
// ch[i][0] 代表左儿子，ch[i][1] 代表右儿子
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];
struct Splay {
    void maintain(int x) {  // 在改变节点位置后，将节点 x 的 size 更新
        sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];
    }
    bool get(int x) {  // 判断节点 x 是父亲节点的左儿子还是右儿子，左儿子返回 0，右儿子返回 1
        return x == ch[fa[x]][1];
    }
    void clear(int x) {  // 销毁节点 x
        ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;
    }
    void rotate(int x) {  // 旋转
        int y = fa[x], z = fa[y], chk = get(x);
        ch[y][chk] = ch[x][chk ^ 1];
        if (ch[x][chk ^ 1]) {
            fa[ch[x][chk ^ 1]] = y;
        }
        ch[x][chk ^ 1] = y;
        fa[y] = x, fa[x] = z;
        if (z) {
            ch[z][y == ch[z][1]] = x;
        }
        maintain(y);
        maintain(x);
    }
    void splay(int x) {
        for (int f = fa[x]; f = fa[x], f; rotate(x)) {
            if (fa[f]) {
                rotate(get(x) == get(f) ? f : x);
            }
        }
        rt = x;
    }
    void splay(int x, int k) {  // 将 x 旋转到 k 下方
        while (fa[x] != k) {
            int y = fa[x], z = fa[y];
            if (z != k) {
                if ((ch[y][1] == x) ^ (ch[z][1] == y)) {
                    rotate(x);
                } else {
                    rotate(y);
                }
            }
            rotate(x);
        }
        if (!k) {
            rt = x;
        }
    }
    void ins(int k) {  // 向树中插入值 k
        if (!rt) {  // 如果树空了，则直接插入根并退出
            val[++tot] = k;
            cnt[tot]++;
            rt = tot;
            maintain(rt);
            return;
        }
        int cur = rt, f = 0;
        while (true) {
            if (val[cur] == k) {  // 如果当前节点的权值等于 k，则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 splay 操作
                cnt[cur]++;
                maintain(cur);
                maintain(f);
                splay(cur);
                break;
            }
            // 按照二叉查找树的性质向下找，找到空节点就插入即可（记得进行 splay 操作）
            f = cur;
            cur = ch[cur][val[cur] < k];
            if (!cur) {
                val[++tot] = k;
                cnt[tot]++;
                fa[tot] = f;
                ch[f][val[f] < k] = tot;
                maintain(tot);
                maintain(f);
                splay(tot);
                break;
            }
        }
    }
    int rk(int k) {  // 查询值 k 的排名（兼具将 k 旋转到根部的作用）
        int res = 0, cur = rt;
        while (true) {
            if (k < val[cur]) {
                cur = ch[cur][0];
            } else {
                res += sz[ch[cur][0]];
                if (k == val[cur]) {
                    splay(cur);
                    return res + 1;
                }
                res += cnt[cur];
                cur = ch[cur][1];
            }
        }
    }
    int kth(int k) {  // 查询排名为 k 的数
        int cur = rt;
        while (true) {
            pushDown(cur);
            if (ch[cur][0] && k <= sz[ch[cur][0]]) {
                cur = ch[cur][0];
            } else {
                k -= cnt[cur] + sz[ch[cur][0]];
                if (k <= 0) {
                    splay(cur);
                    return val[cur];  // 注意，如果想取到排名为 cur 的数的下标，应该返回 cur
                }
                cur = ch[cur][1];
            }
        }
    }
    // 查询前驱 / 后继代表已经将 k 插入，k已经位于根部
    // 返回值取 val 才是前驱 / 后继值
    int pre() {  // 查询前驱(小于 k 的最大的数)
        int cur = ch[rt][0];
        if (!cur) {
            return cur;
        }
        while (ch[cur][1]) {
            cur = ch[cur][1];
        }
        splay(cur);
        return cur;
    }
    int nxt() {  // 查询后继(大于 k 的最小的数)
        int cur = ch[rt][1];
        if (!cur) {
            return cur;
        }
        while (ch[cur][0]) {
            cur = ch[cur][0];
        }
        splay(cur);
        return cur;
    }
    void del(int k) {  // 删除值 k
        rk(k);  // 将 k 转到根部
        if (cnt[rt] > 1) {
            cnt[rt]--;
            maintain(rt);
            return;
        }
        if (!ch[rt][0] && !ch[rt][1]) {  // 左子树右子树都不存在
            clear(rt);
            rt = 0;
            return;
        }
        if (!ch[rt][0]) {  // 左子树不存在
            int cur = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(cur);
            return;
        }
        if (!ch[rt][1]) {  // 右子树不存在
            int cur = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(cur);
            return;
        }
        // 合并左右子树
        int cur = rt, x = pre();
        fa[ch[cur][1]] = x;
        ch[x][1] = ch[cur][1];
        clear(cur);
        maintain(rt);
    }
};