【模板】文艺平衡树

形式化题目

初始序列为 $[1,2,\dots,n]$ 。每次操作给出区间 $[l,r]$ ，把其中元素的相对顺序完全翻转；完成所有操作后输出最终序列。

解法总览

普通数组翻转一次需要 $O(r-l+1)$ ，最坏会达到 $O(nm)$ 。本题的关键是把数组看成一棵“中序遍历等于序列顺序”的平衡树。这样只要把区间单独切出来，对它打一个翻转标记，再拼回去即可。

解法	如何切出 $[l,r]$	翻转方式	单次复杂度
隐式 Splay	两个哨兵节点夹住目标区间	中段根打 `rev` 标记	$O(\log n)$
隐式 FHQ-Treap	两次按排名 `split`	中段根打 `rev` 标记	期望 $O(\log n)$

两种写法都维护子树大小 size，用它把“第几个元素”转化为树上的位置。

解法一：隐式 Splay

思路

在真实序列两端各加一个哨兵，序列变成 $[0,1,2,\dots,n,n+1]$ 。

要翻转真实区间 $[l,r]$ 时：

找到它左边的节点，即扩展序列中的第 $l$ 个节点，并 Splay 到根；
找到它右边的节点，即第 $r+2$ 个节点，并 Splay 到根的右儿子；
此时右儿子的左子树恰好是 $[l,r]$ ，给这棵子树的 rev 异或一次；
访问子树时再下传标记：交换左右儿子，并把标记传给两个儿子。

Splay 旋转之前必须先将根到当前节点路径上的翻转标记全部下传，否则左右儿子的实际方向会与记录不一致。

代码

cpp

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163/*-----------------
* author: Rainboy
* email: rainboylvx@qq.com
* time: 2019年 11月 19日 星期二 15:17:14 CST
* problem: luogu-3391
*----------------*/
#include <bits/stdc++.h>
using namespace std;

// 这里是 Splay 写法；文件名沿用原来的 main-treap.cpp。
const int MAXN = 100000 + 5;

struct Node {
    int fa, ch[2], val, size;
    bool rev;
} spl[MAXN];

int n, m;
int root, node_count;

int get_size(int u) {
    return spl[u].size;
}

void push_up(int u) {
    spl[u].size = get_size(spl[u].ch[0]) + get_size(spl[u].ch[1]) + 1;
}

void push_down(int u) {
    if (!u || !spl[u].rev) return;
    swap(spl[u].ch[0], spl[u].ch[1]);
    spl[spl[u].ch[0]].rev ^= 1;
    spl[spl[u].ch[1]].rev ^= 1;
    spl[u].rev = false;
}

bool ident(int x) {
    return spl[spl[x].fa].ch[1] == x;
}

void connect(int x, int fa, int side) {
    spl[fa].ch[side] = x;
    if (x) spl[x].fa = fa;
}

void rotate(int x) {
    int f = spl[x].fa;
    int ff = spl[f].fa;
    int side = ident(x);

    connect(spl[x].ch[side ^ 1], f, side);
    connect(f, x, side ^ 1);
    connect(x, ff, spl[ff].ch[1] == f);
    push_up(f);
    push_up(x);
}

// 旋转前先把祖先的翻转标记全部下传，避免左右儿子方向过期。
void push_all(int x, int top) {
    if (spl[x].fa != top) push_all(spl[x].fa, top);
    push_down(x);
}

void splay(int x, int top) {
    push_all(x, top);
    while (spl[x].fa != top) {
        int f = spl[x].fa;
        int ff = spl[f].fa;
        if (ff != top) {
            if (ident(x) == ident(f)) rotate(f);
            else rotate(x);
        }
        rotate(x);
    }
    if (!top) root = x;
}

void new_node(int val) {
    int u = ++node_count;
    spl[u].val = val;
    spl[u].size = 1;
    root = u;
}

// 将新元素接到当前序列末尾。
void append(int val) {
    if (!root) {
        new_node(val);
        return;
    }

    int u = root;
    while (spl[u].ch[1]) {
        push_down(u);
        u = spl[u].ch[1];
    }
    int v = ++node_count;
    spl[v].val = val;
    spl[v].size = 1;
    connect(v, u, 1);
    splay(v, 0);
}

// 返回当前序列第 k 个元素所在节点，k 从 1 开始。
int kth(int k) {
    int u = root;
    while (u) {
        push_down(u);
        int left_size = get_size(spl[u].ch[0]);
        if (k <= left_size) u = spl[u].ch[0];
        else if (k == left_size + 1) return u;
        else {
            k -= left_size + 1;
            u = spl[u].ch[1];
        }
    }
    return 0;
}

void reverse_range(int l, int r) {
    // 序列两端额外放 0 与 n + 1 两个哨兵。
    // 所以第 l 个真实元素左边的边界是第 l 个节点。
    int left_boundary = kth(l);
    splay(left_boundary, 0);
    int right_boundary = kth(r + 2);
    splay(right_boundary, left_boundary);

    int middle = spl[right_boundary].ch[0];
    spl[middle].rev ^= 1;
}

void output(int u, bool &first) {
    if (!u) return;
    push_down(u);
    output(spl[u].ch[0], first);
    if (spl[u].val != 0 && spl[u].val != n + 1) {
        if (!first) cout << ' ';
        cout << spl[u].val;
        first = false;
    }
    output(spl[u].ch[1], first);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i <= n + 1; i++) {
        append(i);
    }

    while (m--) {
        int l, r;
        cin >> l >> r;
        reverse_range(l, r);
    }

    bool first = true;
    output(root, first);
    cout << '\n';
    return 0;
}

复杂度

建树与每次区间翻转均摊 $O(\log n)$ ，总时间复杂度为 $O((n+m)\log n)$ ，空间复杂度为 $O(n)$ 。

解法二：隐式 FHQ-Treap

思路

FHQ-Treap 的普通模板按“值”分裂有序集合；这里的中序顺序代表序列位置，所以将 split(u,k) 改为：左树保留前 $k$ 个元素，右树保留剩余元素。

翻转 $[l,r]$ 分成三步：

text

1
2split(root, r)       -> [1, r] 与 [r+1, n]
split([1, r], l - 1) -> [1, l-1]、[l, r]

对中段根打 rev 标记，再按原顺序合并三段即可。merge 时也要先下传标记，确保递归合并的左右子树是真实顺序。

rbook 的 FHQ-Treap 模板说明中，split / merge / size 是核心接口；本题只将“按值分裂”替换成“按排名分裂”，并增加区间翻转标记。

图示：两次重叠翻转中的懒标记

下面固定初始序列为 $[1,2,3,4,5,6,7,8]$ ，依次翻转 $[2,6]$ 和 $[3,7]$ 。为了让树形稳定，图中不用代码生成的随机大整数，而人为指定优先级：

value	1	2	3	4	5	6	7	8
pri	50	70	30	100	40	80	20	60

每个节点都写出 value / pri / size / rev。橙色表示 rev=1，它只说明整棵子树“将要翻转”，并不表示所有后代已立即交换；蓝色边表示本步 push_down 刚交换过该节点的左右子树。所有图均由 fhq_treap_viz.py 生成。

步骤 0：初始树

调用：merge(1), merge(2), ..., merge(8)。

初始隐式 FHQ-Treap，所有节点列出 value、pri、size、rev

中序遍历是初始序列 1 2 3 4 5 6 7 8。此时 size 已保存每个子树的元素个数，所以 split 可以按排名工作。

步骤 1：切出第一次翻转区间 `[2,6]`

调用：split(root, 6)，再调用 split(first, 1)。

两次分裂后，三部分依次是“位置 1”“位置 2 到 6”“位置 7 到 8”。这里写的是位置范围，不是节点的 value；注意每棵树的 size 已在断边回溯时重新计算。

步骤 2：只给中段根打标记

调用：middle.rev ^= 1。

橙色根表示整个 [2,6] 需要翻转。这里没有递归访问后代，因此一次区间翻转本身不需要线性时间。

步骤 3：第一次合并时按需下传

调用：root = merge(merge(before, middle), last)。

merge 为了继续递归，访问到带标记的节点才执行 push_down。蓝色边记录本步发生的左右交换；这就是 lazy 的含义：用到时才做。

步骤 4：第二次翻转重新按位置切开

调用：split(root, 7)，再调用 split(first, 2)。

第二次操作与第一次重叠，但不必展开整个序列。沿着 split 的访问路径，遗留的 rev 会自然下传；最终仍切成前缀、中段、后缀三棵树。

步骤 5：第二个中段继续延迟翻转

调用：middle.rev ^= 1。

rev 使用异或而不是赋值：同一段被翻转两次时，1 xor 1 = 0，恰好恢复原顺序。

步骤 6：合并回最终的树形

调用：root = merge(merge(before, middle), last)。

pri 只决定 Treap 的树形和 merge 选哪个根；元素的先后顺序始终由中序遍历决定，两者不能混淆。

步骤 7：输出时清理剩余标记

调用：中序遍历中的 push_down(node)。

访问节点前下传标记后，中序遍历得到最终答案：1 6 7 2 3 4 5 8。这说明翻转标记可以一直留在未访问的子树根上，直到下次 split、merge 或输出真正需要它。

C++ 代码

cpp

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-09-14 19:06
 * update_at: 2026-09-14 19:06
 */
#include <bits/stdc++.h>
using namespace std;

// 隐式 FHQ-Treap：中序遍历顺序就是当前序列顺序，split 按元素个数分裂。

const int MAXN = 100000 + 5;

struct Node {
    int l, r;
    int size;
    unsigned int fix;
    int val;
    bool rev;
} tr[MAXN];

int n, m;
int root, node_count;
mt19937 rng(233);

int get_size(int u) {
    return tr[u].size;
}

int new_node(int val) {
    int u = ++node_count;
    tr[u].l = tr[u].r = 0;
    tr[u].size = 1;
    tr[u].fix = rng();
    tr[u].val = val;
    tr[u].rev = false;
    return u;
}

void push_up(int u) {
    tr[u].size = get_size(tr[u].l) + get_size(tr[u].r) + 1;
}

void push_down(int u) {
    if (!u || !tr[u].rev) return;
    swap(tr[u].l, tr[u].r);
    tr[tr[u].l].rev ^= 1;
    tr[tr[u].r].rev ^= 1;
    tr[u].rev = false;
}

// x 包含前 k 个元素，y 包含其余元素。
void split(int u, int k, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }

    push_down(u);
    if (get_size(tr[u].l) >= k) {
        y = u;
        split(tr[u].l, k, x, tr[y].l);
        push_up(y);
    } else {
        x = u;
        split(tr[u].r, k - get_size(tr[u].l) - 1, tr[x].r, y);
        push_up(x);
    }
}

// 合并两段相邻序列：x 的全部元素排在 y 的前面。
int merge(int x, int y) {
    if (!x || !y) return x + y;

    if (tr[x].fix > tr[y].fix) {
        push_down(x);
        tr[x].r = merge(tr[x].r, y);
        push_up(x);
        return x;
    }

    push_down(y);
    tr[y].l = merge(x, tr[y].l);
    push_up(y);
    return y;
}

void reverse_range(int l, int r) {
    int left_part, middle_part, right_part;
    split(root, r, left_part, right_part);
    split(left_part, l - 1, left_part, middle_part);

    // 只翻转中段根的左右儿子，真正访问子树时再下传。
    tr[middle_part].rev ^= 1;
    root = merge(merge(left_part, middle_part), right_part);
}

void output(int u, bool &first) {
    if (!u) return;
    push_down(u);
    output(tr[u].l, first);
    if (!first) cout << ' ';
    cout << tr[u].val;
    first = false;
    output(tr[u].r, first);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        root = merge(root, new_node(i));
    }

    while (m--) {
        int l, r;
        cin >> l >> r;
        reverse_range(l, r);
    }

    bool first = true;
    output(root, first);
    cout << '\n';
    return 0;
}

Python 代码

python

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
110
111
112
113
114
115
116
117
118
119
120
121"""洛谷 P3391：隐式 FHQ-Treap 区间翻转。"""

import random
import sys


sys.setrecursionlimit(300000)


class Node:
    """模板节点增加 rev，用于懒标记区间翻转。"""

    __slots__ = ("val", "pri", "size", "left", "right", "rev")

    def __init__(self, val, pri):
        self.val = val
        self.pri = pri
        self.size = 1
        self.left = None
        self.right = None
        self.rev = False


class ImplicitFHQTreap:
    """中序遍历表示序列；split 按元素个数而非数值分裂。"""

    def __init__(self):
        self.root = None
        self.rng = random.Random(233)

    def size(self, u):
        return u.size if u is not None else 0

    def push_up(self, u):
        u.size = self.size(u.left) + self.size(u.right) + 1

    def push_down(self, u):
        if u is None or not u.rev:
            return
        u.left, u.right = u.right, u.left
        if u.left is not None:
            u.left.rev = not u.left.rev
        if u.right is not None:
            u.right.rev = not u.right.rev
        u.rev = False

    def new_node(self, val):
        return Node(val, self.rng.randint(1, 2**31 - 1))

    def split(self, u, k):
        """返回前 k 个元素和其余元素组成的两棵树。"""
        if u is None:
            return None, None

        self.push_down(u)
        if self.size(u.left) >= k:
            x, u.left = self.split(u.left, k)
            self.push_up(u)
            return x, u

        u.right, y = self.split(u.right, k - self.size(u.left) - 1)
        self.push_up(u)
        return u, y

    def merge(self, x, y):
        """合并两段相邻序列，x 中元素全部在 y 之前。"""
        if x is None or y is None:
            return x if y is None else y

        if x.pri > y.pri:
            self.push_down(x)
            x.right = self.merge(x.right, y)
            self.push_up(x)
            return x

        self.push_down(y)
        y.left = self.merge(x, y.left)
        self.push_up(y)
        return y

    def append(self, val):
        self.root = self.merge(self.root, self.new_node(val))

    def reverse_range(self, left, right):
        first, last = self.split(self.root, right)
        before, middle = self.split(first, left - 1)
        middle.rev = not middle.rev
        self.root = self.merge(self.merge(before, middle), last)

    def inorder(self, u, answer):
        if u is None:
            return
        self.push_down(u)
        self.inorder(u.left, answer)
        answer.append(str(u.val))
        self.inorder(u.right, answer)


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, m = data[0], data[1]
    treap = ImplicitFHQTreap()
    for value in range(1, n + 1):
        treap.append(value)

    pos = 2
    for _ in range(m):
        left, right = data[pos], data[pos + 1]
        pos += 2
        treap.reverse_range(left, right)

    answer = []
    treap.inorder(treap.root, answer)
    sys.stdout.write(" ".join(answer) + "\n")


if __name__ == "__main__":
    main()

复杂度

每次 split 与 merge 的期望复杂度为 $O(\log n)$ ，总时间复杂度为 $O((n+m)\log n)$ ，空间复杂度为 $O(n)$ 。

总结

文艺平衡树的本质是用平衡树维护“序列位置”，不是维护元素值的大小关系。区间操作先切出中段，再延迟修改中段根，最后合并回去。

Splay 用哨兵把中段变成固定位置的子树；FHQ-Treap 用两次按排名分裂直接得到中段。两种方法都可以迁移到区间移动、插入、删除和区间查询等序列维护问题。