无旋Treap，又叫 FHQ-Treap。

和 Splay 一样，无旋Treap 也是用中序遍历维护序列的，要维护的这个序列是有某种顺序的，对于不同的题目，这个「顺序」的定义是不同的。比如，对于普通平衡树，「顺序」是指按权值递增的顺序；对于文艺平衡树，「顺序」是指按
在数组中下标递增的顺序，我们管按 XXX 递增的顺序的这个 XXX 叫顺序值。

无旋Treap 即是顺序值满足 BST 的性质，每个点的随机值（这个随机值会在每个点被创建的时候随机生成，且永远不会改变）满足大根堆的性质的二叉查找树。

核心操作有两个：Split(id,v)\text{Split}(id, v) 和 Merge(id1,id2)\text{Merge}(id_1,id_2)。

{lrt,rrt}Split(id,v)\{lrt,rrt\}\text{Split}(id, v)：将 subtreeid\text{subtree}_{id} 分成两棵树，一颗根为 lrtlrt，满足 ∀i∈subtreelrt,vali≤v\forall i\in\text{subtree}_{lrt},val_i\le v（valival_i 为点 ii 的顺序值）；另一颗根为 rrtrrt，满足 ∀i∈subtreerrt,vali>v\forall i\in\text{subtree}_{rrt},val_i>v。

{rt}Merge(id1,id2)\{rt\}\text{Merge}(id_1,id_2)：保证对于 ∀i∈subtreeid1,j∈subtreeid2\forall i\in\text{subtree}_{id_1},j\in\text{subtree}_{id_2} 有 vali<valjval_i<val_j，合并 subtreeid1\text{subtree}_{id_1} 和 subtreeid2\text{subtree}_{id_2}，最后根为 rtrt。

Luogu P3369 【模板】普通平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
mt19937 rd(time(0));

int root;
int cntnd;
int son[MAXn + 10][2];
int val[MAXn + 10], pval[MAXn + 10], cnt[MAXn + 10], siz[MAXn + 10];
inline void pushup(int id) {
    siz[id] = siz[son[id][0]] + siz[son[id][1]] + cnt[id];
}
inline void initnode(int id, int v, int ct) {
    val[id] = v;
    pval[id] = rd();
    cnt[id] = ct;
    siz[id] = ct;
}
pair<int, int> Split(int id, int v) {
    if (id == 0) return make_pair(0, 0);
    int lrt, rrt;
    if (val[id] <= v) {
        tie(lrt, rrt) = Split(son[id][1], v);
        son[id][1] = lrt;
        pushup(id);
        return make_pair(id, rrt);
    } else {
        tie(lrt, rrt) = Split(son[id][0], v);
        son[id][0] = rrt;
        pushup(id);
        return make_pair(lrt, id);
    }
}
int Merge(int id1, int id2) {
    if (id1 == 0 || id2 == 0) return id1 + id2;
    if (pval[id1] >= pval[id2]) {
        son[id1][1] = Merge(son[id1][1], id2);
        pushup(id1);
        return id1;
    } else {
        son[id2][0] = Merge(id1, son[id2][0]);
        pushup(id2);
        return id2;
    }
}
void Insert(int v) {
    int lrt, mrt, rrt;
    tie(lrt, rrt) = Split(root, v - 1);
    tie(mrt, rrt) = Split(rrt, v);
    if (mrt) {
        ++cnt[mrt];
        pushup(mrt);
    } else {
        mrt = ++cntnd;
        initnode(mrt, v, 1);
    }
    root = Merge(Merge(lrt, mrt), rrt);
}
void Delete(int v) {
    int lrt, mrt, rrt;
    tie(lrt, rrt) = Split(root, v - 1);
    tie(mrt, rrt) = Split(rrt, v);
    if (mrt) {
        --cnt[mrt];
        pushup(mrt);
        if (cnt[mrt]) lrt = Merge(lrt, mrt);
    }
    root = Merge(lrt, rrt);
}
int ValtoRank(int v) {
    int lrt, rrt;
    tie(lrt, rrt) = Split(root, v - 1);
    int ans = siz[lrt] + 1;
    root = Merge(lrt, rrt);
    return ans;
}
int RanktoId(int rk) {
    int id = root;
    while (true) {
        if (rk <= siz[son[id][0]]) {
            id = son[id][0];
        } else if (rk <= siz[son[id][0]] + cnt[id]) {
            return id;
        } else {
            rk -= siz[son[id][0]] + cnt[id];
            id = son[id][1];
        }
    }
    return id;
}
int PreId(int v) {
    int lrt, rrt;
    tie(lrt, rrt) = Split(root, v - 1);
    int lrtmx = lrt;
    while (true) {
        if (son[lrtmx][1]) lrtmx = son[lrtmx][1];
        else break;
    }
    root = Merge(lrt, rrt);
    return lrtmx;
}
int NexId(int v) {
    int lrt, rrt;
    tie(lrt, rrt) = Split(root, v);
    int rrtmn = rrt;
    while (true) {
        if (son[rrtmn][0]) rrtmn = son[rrtmn][0];
        else break;
    }
    root = Merge(lrt, rrt);
    return rrtmn;
}

Luogu P3391 【模板】文艺平衡树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
mt19937 rd(time(0));

int root;
int cntnd;
int son[MAXn + 10][2];
int val[MAXn + 10], pval[MAXn + 10], siz[MAXn + 10];
int lzrev[MAXn + 10];
inline void putrev(int id) {
    swap(son[id][0], son[id][1]);
    lzrev[id] ^= 1;
}
inline void pushdown(int id) {
    if (lzrev[id]) {
        putrev(son[id][0]);
        putrev(son[id][1]);
        lzrev[id] = 0;
    }
}
inline void pushup(int id) {
    siz[id] = siz[son[id][0]] + siz[son[id][1]] + 1;
}
inline void initnode(int id, int v) {
    val[id] = v;
    pval[id] = rd();
    siz[id] = 1;
}
pair<int, int> Split(int id, int p) {
    if (p == 0) return make_pair(0, id);
    if (id == 0) return make_pair(0, 0);
    pushdown(id);
    int lrt, rrt;
    if (p <= siz[son[id][0]]) {
        tie(lrt, rrt) = Split(son[id][0], p);
        son[id][0] = rrt;
        pushup(id);
        return make_pair(lrt, id);
    } else if (p <= siz[son[id][0]] + 1) {
        lrt = id;
        rrt = son[id][1];
        son[id][1] = 0;
        pushup(id);
        return make_pair(lrt, rrt);
    } else {
        tie(lrt, rrt) = Split(son[id][1], p - (siz[son[id][0]] + 1));
        son[id][1] = lrt;
        pushup(id);
        return make_pair(id, rrt);
    }
}
int Merge(int id1, int id2) {
    if (id1 == 0 || id2 == 0) return id1 + id2;
    pushdown(id1);
    pushdown(id2);
    if (pval[id1] >= pval[id2]) {
        son[id1][1] = Merge(son[id1][1], id2);
        pushup(id1);
        return id1;
    } else {
        son[id2][0] = Merge(id1, son[id2][0]);
        pushup(id2);
        return id2;
    }
}
void Build(int n) {
    for (int i = 1; i <= n; ++i) {
        initnode(++cntnd, i);
        root = Merge(root, cntnd);
    }
}
void Traversal(int id) {
    if (id == 0) return;
    pushdown(id);
    Traversal(son[id][0]);
    printf("%d ", val[id]);
    Traversal(son[id][1]);
}
void Reverse(int l, int r) {
    int lrt, mrt, rrt;
    tie(lrt, rrt) = Split(root, l - 1);
    tie(mrt, rrt) = Split(rrt, r - (l - 1));
    putrev(mrt);
    root = Merge(Merge(lrt, mrt), rrt);
}