Treap

参考资料
http://www.yhzq-blog.cc/fhq-treap%e6%80%bb%e7%bb%93/
实现基本照抄 kactl
感觉有必要，就顺手学一下好了

笛卡尔树

定义 一棵二叉树，节点维护键值对 (key, val)，其中 key 满足堆性质而 val 满足二叉树性质
Treap 即为一棵特殊的笛卡尔树

Treap

结构 Treap为一棵笛卡尔树，其中 val 为所维护的值，而 key 为随机赋予的
由随机堆的性质，这棵树的深度为 O(logn) 级别的
维护 容易考虑用传统的旋转来维护，但是可以用分裂与合并操作来替代，其代码更短
需要维护的值具体有：key, val, cnt, l, r

class Node {
 public:
    int a, y, c = 1;    //val, key, cnt
    Node *l = 0, *r = 0;
    Node(int val) : a(val), y(rnd()) {}
    void recalc() { c = cnt(l) + cnt(r) + 1; }
};

其中随机值推荐使用 mt19937，简单测了一下发现比自己写的线性同余还快（rand()可以爬了）

FHQ-Treap

核心操作

分离 Split 将原树中的前 k 大的节点分裂出去
考虑一个递归过程
要从节点 u 的子树中分出 k 个节点
若左子树数量大于等于 k ，则变为从左子树中分出 k 个节点
否则从右子树中分出 k - cnt(l) - 1 个节点，接到当前节点的右侧，右子树剩下的部分就剩下

//first为被分出去的根，second为剩下部分的根
pair<Node*, Node*> split(Node* u, int k) {
    if (!u) return {};
    if (cnt(u->l) >= k) {
        auto pa = split(u->l, k);
        u->l = pa.second;
        u->recalc();
        return {pa.first, u};
    } else {
        auto pa = split(u->r, k - cnt(u->l) - 1);
        u->r = pa.first;
        u->recalc();
        return {u, pa.second};
    }
}

右合并 Merge 将给定的第二棵树合并到第一棵树的右侧
这里的 右 即为保证前者所有节点的权小于后者的（这里考虑从小到大）
需要注意该操作是不满足交换律的
还是递归处理
要满足BST性质，后者应当放到前者的右侧，或者前者应放到后者的左侧
假如那一侧已经被占了，那就将那一侧与要放的继续合并
再考虑满足堆性质（这里考虑大根堆）

//返回合并后的根
Node* merge(Node* u, Node* v) {
    if (!u) return v;
    if (!v) return u;
    if (u->y > v->y) {
        u->r = merge(u->r, v);
        u->recalc();
        return u;
    } else {
        v->l = merge(u, v->l);
        v->recalc();
        return v;
    }
}

基本操作的拓展

插入 insert 将某棵树插入到另一颗树的第 k + 1 个位置
做法非常简单，先将前 k 个元素拆出来，然后从左至右依次合并即可

Node* insert(Node* u, Node* v, int k) {
    auto pa = split(u, k);
    return merge(merge(pa.first, v), pa.second);
}

BST的操作

查询排名 rnk
按照BST的方法去做就好了

int rnk(Node* u, int val) {
    if (!u) return 0;
    if (u->a < val)
        return cnt(u->l) + 1 + rnd(u->r, val);
    else
        return rnd(u->l, val);
}

排名查元素 kth
可以偷懒，split两次之后merge

int kth(int k) {
    auto pa = split(rt, k);
    auto pb = split(pa.first, k - 1);
    int ret = pb.second->a;
    merge(merge(pb.first, pb.second), pa.second);
    return ret;
}

插入元素 push
结合rnd与insert就变成了push

void push(int val) {
    nodes[n] = Node(val);
    rt = n ? insert(rt, nodes + n, rnk(rt, val)) : nodes;
    n += 1;
}

弹出元素 pop
偷懒，用split和rnk拆出比它小的，然后剩下部分再拆掉第一个

void pop(int val) {
    auto pa = split(rt, rnk(rt, val));
    rt = merge(pa.first, split(pa.second, 1).second);
}

求前驱 pre 与 求后继 suc
偷懒，还是求个rnk然后拆

int pre(int val) {
    int k = rnk(rt, val);
    auto pa = split(rt, k);
    auto pb = split(pa.first, k - 1);
    int ret = pb.second->a;
    rt = merge(merge(pb.first, pb.second), pa.second);
    return ret;
}
int suc(int val) {
    int k = rnk(rt, val + 1);
    auto pa = split(rt, k);
    auto pb = split(pa.second, 1);
    int ret = pb.first->a;
    rt = merge(pa.first, merge(pb.first, pb.second));
    return ret;
}

另外，容易发现，按照上面那么做，就能处理重复元素的情况
结合上述内容，模板题就搞定了

洛谷P6136 【模板】普通平衡树（数据加强版）

#include <iostream>
#include <random>
using namespace std;

const int MAX_N = 1E6 + 1E5 + 100;

mt19937 rnd(114514);

class Treap {
private:
    class Node {
    public:
        int a, y, c = 1;
        Node *l = 0, *r = 0;
        Node(int val = 0) : a(val), y(rnd()) {}
        void recalc() { c = cnt(l) + cnt(r) + 1; }
    };
    //=============

    static int cnt(Node* u) { return u ? u->c : 0; }

    //============

    int n;
    Node* rt;
    Node nodes[MAX_N];

    //============

    pair<Node*, Node*>
    split(Node* u, int k) {
        if (!u) return {};
        if (cnt(u->l) >= k) {
            auto pa = split(u->l, k);
            u->l = pa.second;
            u->recalc();
            return {pa.first, u};
        } else {
            auto pa = split(u->r, k - cnt(u->l) - 1);
            u->r = pa.first;
            u->recalc();
            return {u, pa.second};
        }
    }

    Node* merge(Node* u, Node* v) {
        if (!u) return v;
        if (!v) return u;
        if (u->y > v->y) {
            u->r = merge(u->r, v);
            u->recalc();
            return u;
        } else {
            v->l = merge(u, v->l);
            v->recalc();
            return v;
        }
    }

    Node* insert(Node* u, Node* v, int k) {
        auto pa = split(u, k);
        return merge(merge(pa.first, v), pa.second);
    }

    //=======================

    int rnk(Node* u, int val) {
        if (!u) return 0;
        if (u->a < val)
            return cnt(u->l) + 1 + rnk(u->r, val);
        else
            return rnk(u->l, val);
    }

public:
    int rnk(int val) {
        return rnk(rt, val) + 1;
    }

    int kth(int k) {
        auto pa = split(rt, k);
        auto pb = split(pa.first, k - 1);
        int ret = pb.second->a;
        rt = merge(merge(pb.first, pb.second), pa.second);
        return ret;
    }

    void push(int val) {
        nodes[n] = Node(val);
        rt = n ? insert(rt, nodes + n, rnk(rt, val)) : nodes;
        n += 1;
    }

    void pop(int val) {
        auto pa = split(rt, rnk(rt, val));
        rt = merge(pa.first, split(pa.second, 1).second);
    }

    int pre(int val) {
        int k = rnk(rt, val);
        auto pa = split(rt, k);
        auto pb = split(pa.first, k - 1);
        int ret = pb.second->a;
        rt = merge(merge(pb.first, pb.second), pa.second);
        return ret;
    }

    int suc(int val) {
        int k = rnk(rt, val + 1);
        auto pa = split(rt, k);
        auto pb = split(pa.second, 1);
        int ret = pb.first->a;
        rt = merge(pa.first, merge(pb.first, pb.second));
        return ret;
    }
};

//=========================

int read() {
    int x = 0;
    char c = getchar();
    while ('0' > c || c > '9') c = getchar();
    while ('0' <= c && c <= '9') {
        x *= 10;
        x += c - '0';
        c = getchar();
    }
    return x;
}

char wBuf[10];
void write(int x) {
    if (!x) putchar('0');
    int cnt = 0;
    while (x) {
        wBuf[cnt++] = x % 10 + '0';
        x /= 10;
    }
    while (cnt) putchar(wBuf[--cnt]);
}

//=========================

int n, m, lst, ans;
Treap tr;

signed main() {
    n = read(), m = read();
    for (int i = 0; i < n; ++i) {
        int u = read();
        tr.push(u);
    }
    for (int i = 0; i < m; ++i) {
        int opt = read(), x = read() ^ lst;
        switch (opt) {
        case 1:
            tr.push(x);
            break;
        case 2:
            tr.pop(x);
            break;
        case 3:
            ans ^= lst = tr.rnk(x);
            break;
        case 4:
            ans ^= lst = tr.kth(x);
            break;
        case 5:
            ans ^= lst = tr.pre(x);
            break;
        case 6:
            ans ^= lst = tr.suc(x);
            break;
        }
    }
    write(ans);
    putchar('\n');

    return 0;
}

结果看，在偷了不少懒的情况下，平均比splay要稍快
而代码短了很多
其实可以发现，要实现这样的数据结构，关键在于两个基本操作以及 rnk
实际上 rnk 与 split 可以合并成按照权值进行分裂的版本（以下代码没测过）

//分裂出权值小于 k 的
pair<Node*, Node*> split(Node* u, int k) {
    if (!u) return {};
    if (u->a >= k) {
        auto pa = split(u->l, k);
        u->l = pa.second;
        u->recalc();
        return {pa.first, u};
    } else {
        auto pa = split(u->r, k - cnt(u->l) - 1);
        u->r = pa.first;
        u->recalc();
        return {u, pa.second};
    }
}

这么做的话可以减少一些常数，不过也有缺点

重要拓展

容易发现，数量版本的核心操作是不关心 val 的具体取值的，这一点与 Splay 非常相似
也就是说并不是实际上维护了BST本身，而是在满足 前者的权小于后者 的前提
更进一步地说，这是在维护这个序列本身，可以做一些区间操作
以区间翻转举例

区间翻转 flip
分成三步：提取区间，打标记，合并区间

auto pa = split(rt, r);
auto pb = split(pa.first, l - 1);
//提取的目标区间为 pb.second
pb.second->flip ^= 1;
//打上标记
rt = merge(merge(pb.first, pb.second), pa.second);
//合并区间

标记还需要具体实现，因此需要增加个pushFilp，有事没事下放一下

void Node::pushFlip() {
    if (flip) {
        flip = 0;
        if (l) l->flip ^= 1;
        if (r) r->flip ^= 1;
        swap(l, r);
    }
}

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

#include <iostream>
#include <random>
using namespace std;

const int MAX_N = 1E5 + 100;
mt19937 rnd(114514);

class Treap {
private:
    class Node {
    public:
        int a, k, c = 1;
        bool flip = 0;
        Node *l = 0, *r = 0;
        Node(int _a = 0) : a(_a), k(rnd()) {}
        void recalc() { c = cnt(l) + cnt(r) + 1; }
        void pushFlip() {
            if (flip) {
                flip = 0;
                if (l) l->flip ^= 1;
                if (r) r->flip ^= 1;
                swap(l, r);
            }
        }
    };

    int n;
    Node* rt;
    Node nodes[MAX_N];

    //==============

    static int cnt(Node* u) { return u ? u->c : 0; }

    pair<Node*, Node*> split(Node* u, int k) {
        if (!u) return {};
        u->pushFlip();
        if (cnt(u->l) >= k) {
            auto pa = split(u->l, k);
            u->l = pa.second;
            u->recalc();
            return {pa.first, u};
        } else {
            auto pa = split(u->r, k - cnt(u->l) - 1);
            u->r = pa.first;
            u->recalc();
            return {u, pa.second};
        }
    }

    Node* merge(Node* u, Node* v) {
        if (!u) return v;
        if (!v) return u;
        u->pushFlip();
        v->pushFlip();
        if (u->k < v->k) {
            v->l = merge(u, v->l);
            v->recalc();
            return v;
        } else {
            u->r = merge(u->r, v);
            u->recalc();
            return u;
        }
    }

    void print(Node* u) {
        if (!u) return;
        u->pushFlip();
        print(u->l);
        cout << u->a << ' ';
        print(u->r);
    }

public:
    void init(int _n) {
        n = _n;
        nodes[0] = Node(1);
        rt = nodes;
        for (int i = 1; i < n; ++i) {
            nodes[i] = Node(i + 1);
            rt = merge(rt, nodes + i);
        }
    }

    void flip(int l, int r) {
        auto pa = split(rt, r);
        auto pb = split(pa.first, l - 1);
        pb.second->flip ^= 1;
        rt = merge(merge(pb.first, pb.second), pa.second);
    }

    void print() {
        print(rt);
    }
};

int n, m;
Treap tr;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    tr.init(n);
    while (m--) {
        int l, r;
        cin >> l >> r;
        tr.flip(l, r);
    }
    tr.print();

    return 0;
}

效率差不多，和splay一比又短了

Link-Cut-Tree

既然这玩意能区间翻转了，那也就能做LCT了
（留个坑