[SCOI2014] 方伯伯的OJ

形式化题目

维护一个长度始终为 $n$ 、元素互不相同的整数序列，初始为 $[1,2,\ldots,n]$ 。每次操作的参数先减去上次输出，随后执行以下操作之一：

将存在的元素 $x$ 改名为当前不存在的元素 $y$ ，位置不变；
将元素 $x$ 移到序列首部或尾部；
查询当前第 $k$ 个元素。

每次操作后输出被改名或移动元素原来的位置，或第 $k$ 个元素的值。

解法总览

直接保存整个序列需要 $O(n)$ 空间，无法承受。真正被单独改名或移动的用户不超过 $m$ 个；其余用户始终成段地连续出现。因此两种解法都把一段连续 ID 打包成一个区间块，只有操作触及块内部的用户时才将其撕裂。

两者的区别只在于“怎样从顺序得到排名、怎样按排名找人”：

解法	顺序的表示	按排名找人	代码
解法一	绝对坐标轴上哪些位置被占用	线段树第 $k$ 小	`main-sgt.cpp`
解法二	FHQ-Treap 的中序遍历	按用户数分裂 Treap	`main-fhq.cpp`

正文以解法一为正式主解：它把“排名”直接化为坐标轴上的前缀人数。解法二给出不建立绝对坐标的等价做法。

解法一：绝对坐标 + 动态开点权值线段树

思路

把初始用户放到坐标区间 $[m+1,m+n]$ ，左边和右边各预留 $m$ 个空坐标。以后置顶就占用一个新的最左坐标，置底就占用一个新的最右坐标。因此当前排名为

rank(pos)=\#\{q\mid q\leqslant pos,\ q\text{ 被占用}\}。

这正是坐标上的前缀和；第 $k$ 名则是第 $k$ 个被占用坐标。动态开点权值线段树维护坐标区间的人数，支持单点赋值、前缀和和第 $k$ 小。

困难在于：线段树只知道某坐标是否有人，不知道这个人是谁。将当前 ID 集合和当前被占用坐标集合记为 $I,P$ ，它们之间存在双射

\varphi:I\longrightarrow P, \qquad \varphi(id)=\text{用户 }id\text{ 所在坐标}。

若一块 ID 区间 $[L,R]$ 从 start_pos 开始连续摆放，则块内的双射是

\varphi(x)=start\_pos+x-L\qquad(L\leqslant x\leqslant R).

所以 id_map 记录 $[L,R]\to start\_pos$ ，pos_map 记录反函数的区间起点。二者不是两份无关的表，而是同一双射和其反函数的两种索引。

要单独操作 $x$ 时，若它在 $[L,R]$ 内部，就把该块细化为

[L,x-1],\quad[x,x],\quad[x+1,R]。

三个块的坐标起点依次为 start_pos、start_pos + x - L、start_pos + x - L + 1。这一步不移动任何用户，只让 $x$ 成为可独立修改的单点。

之后四种操作都很直接：改名只修改单点块的 ID；置顶或置底先把旧坐标赋为 $0$ ，再把新的预留坐标赋为 $1$ ；查询第 $k$ 名时先在线段树上找到坐标，再通过 pos_map 反查 ID。

初始的 $n$ 个连续 $1$ 也不能逐点建树。代码把未开点的区间解释为“尚未被操作、仍保持初始状态”，用该区间与 $[m+1,m+n]$ 的交集大小计算默认人数。于是只会为实际修改经过的路径开点。

正确性

区间块细化前后，对块内每个 ID 使用的坐标公式相同，故双射 $\varphi$ 及其反函数不变。改名只替换定义域中的一个标签；置顶、置底先释放旧坐标再占用一个从未使用的预留坐标，仍然保持一一对应。因此两张 map 始终正确描述 ID 与坐标的对应关系。

线段树叶子值恰为每个坐标是否被占用，故其前缀和正是该坐标上用户的排名。在线段树上比较左右儿子的用户数并下行，得到的恰是第 $k$ 个被占用坐标。再取 $\varphi^{-1}$ ，便得到第 $k$ 名的 ID。四类操作输出均正确。

代码

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

const int MAXM = 1e5 + 5;
const int MAX_NODES = MAXM * 40; // 每次修改最多开 O(log V) 个点

int N, M;
int front_pos, back_pos; // 预留坐标轴的前后指针
int max_pos; // 坐标轴右端点

// ==============================================================================
// 模块一：绝对坐标系下的动态开点线段树 (Absolute Coordinate Segment Tree)
// ==============================================================================

struct SegTree {
    int ls[MAX_NODES], rs[MAX_NODES];
    int sum[MAX_NODES]; // 记录区间内当前存在的真实人数
    int root, tot;

    // 核心魔法：计算任意区间 [l, r] 在“未受到任何操作时”的初始人数
    // 因为一开始所有人都在 [M + 1, M + N] 这个区间内，取交集即可。
    int default_sum(int l, int r) {
        int valid_L = max(l, M + 1);
        int valid_R = min(r, M + N);
        return valid_L <= valid_R ? (valid_R - valid_L + 1) : 0;
    }

    // 向上更新信息
    void push_up(int p, int l, int r) {
        int mid = (l + r) >> 1;
        // 如果左子树存在，取左子树的值；如果不存在，用纯数学公式计算初始值
        int left_val = ls[p] ? sum[ls[p]] : default_sum(l, mid);
        int right_val = rs[p] ? sum[rs[p]] : default_sum(mid + 1, r);
        sum[p] = left_val + right_val;
    }

    // 单点修改：将坐标 pos 处的人数改为 val (1 表示有人，0 表示没人)
    void update(int &p, int l, int r, int pos, int val) {
        // 如果来到一个全新的节点，先给它分配物理内存，并赋予初始默认状态
        if (!p) {
            p = ++tot;
            sum[p] = default_sum(l, r);
        }
        // 触底，修改叶子节点
        if (l == r) {
            sum[p] = val;
            return;
        }
        
        int mid = (l + r) >> 1;
        if (pos <= mid) update(ls[p], l, mid, pos, val);
        else update(rs[p], mid + 1, r, pos, val);
        
        push_up(p, l, r);
    }

    // 查询前缀和：查询坐标轴 [1, pos] 区间内一共有多少人（即该坐标的当前名次 Rank）
    int query_rank(int p, int l, int r, int pos) {
        // 如果节点不存在，说明这片区域处于“处女地”状态，直接用公式 $O(1)$ 结算
        if (!p) return default_sum(max(l, 1), min(r, pos));
        
        if (l == r) return sum[p]; // 触底返回
        
        int mid = (l + r) >> 1;
        if (pos <= mid) {
            return query_rank(ls[p], l, mid, pos);
        } else {
            // 如果跨越了左半区，左半区全拿，去右半区继续找
            int left_val = ls[p] ? sum[ls[p]] : default_sum(l, mid);
            return left_val + query_rank(rs[p], mid + 1, r, pos);
        }
    }

    // 线段树上二分：查找当前排在第 K 位的人所在的绝对坐标
    int query_kth(int p, int l, int r, int k) {
        if (l == r) return l; // 找到了目标坐标
        
        int mid = (l + r) >> 1;
        int left_val = ls[p] ? sum[ls[p]] : default_sum(l, mid);
        
        if (k <= left_val) {
            // 左边人数够，继续去左子树找
            return query_kth(ls[p], l, mid, k);
        } else {
            // 左边不够，减去左边的人数，去右子树找
            return query_kth(rs[p], mid + 1, r, k - left_val);
        }
    }
} tree;

// ==============================================================================
// 模块二：离散数学集合划分 —— Map 动态撕裂机制 (Interval Refinement)
// ==============================================================================

struct Interval {
    int L, R;
    int start_pos; // 这个区间内，L 所对应的绝对坐标
};

// 逻辑系统：维护 用户ID(L) -> 物理区间信息(R, start_pos) 的映射 (Bijection)
map<int, Interval> id_map; 
// 反向映射：为了操作4（查名次），需要 绝对坐标(start_pos) -> 用户ID 的映射
map<int, int> pos_map; 

// 核心函数：找到包含目标 id 的区间，如果它在中间，就“撕裂”它，并返回该 id 的绝对坐标
int split_and_get_pos(int id) {
    auto it = id_map.upper_bound(id);
    --it; // 找到对应的代表元（区间左端点）
    
    int L = it->second.L;
    int R = it->second.R;
    int pos = it->second.start_pos;
    
    // 计算目标 id 在本区间内的相对偏移量
    int target_pos = pos + (id - L); 
    
    // 如果它不是独立的单点区间，触发集合的撕裂 (Refinement)
    if (L != R) {
        id_map.erase(it);
        pos_map.erase(pos);
        
        // 拆分出左半段 [L, id-1]
        if (L <= id - 1) {
            id_map[L] = {L, id - 1, pos};
            pos_map[pos] = L;
        }
        // 拆分出右半段 [id+1, R]
        if (id + 1 <= R) {
            id_map[id + 1] = {id + 1, R, target_pos + 1};
            pos_map[target_pos + 1] = id + 1;
        }
        // 剥离出独立单点 [id, id]
        id_map[id] = {id, id, target_pos};
        pos_map[target_pos] = id;
    }
    
    return target_pos; // 返回目标在坐标轴上的绝对位置
}

// 已知 pos 处有人，查询这个绝对坐标对应的用户编号
int get_id_by_pos(int pos) {
    map<int, int>::iterator it = pos_map.upper_bound(pos);
    --it;
    return it->second + pos - it->first;
}

// 将已经被 split 成单点的用户移动到新位置
void move_user(int id, int old_pos, int new_pos) {
    tree.update(tree.root, 1, max_pos, old_pos, 0);
    tree.update(tree.root, 1, max_pos, new_pos, 1);

    id_map[id] = {id, id, new_pos};
    pos_map.erase(old_pos);
    pos_map[new_pos] = id;
}

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

    cin >> N >> M;

    // 初始用户占据 [M + 1, M + N]，两端各预留 M 个位置给移动操作。
    front_pos = M + 1;
    back_pos = M + N;
    max_pos = N + 2 * M;

    id_map[1] = {1, N, M + 1};
    pos_map[M + 1] = 1;

    int last_answer = 0;
    for (int i = 1; i <= M; i++) {
        int op, x, y;
        cin >> op >> x;
        x -= last_answer;

        if (op == 1) {
            cin >> y;
            y -= last_answer;

            int pos = split_and_get_pos(x);
            last_answer = tree.query_rank(tree.root, 1, max_pos, pos);

            // x 此时已经是独立单点，直接把该单点的编号改成 y。
            id_map.erase(x);
            id_map[y] = {y, y, pos};
            pos_map[pos] = y;
        } else if (op == 2) {
            int pos = split_and_get_pos(x);
            last_answer = tree.query_rank(tree.root, 1, max_pos, pos);

            front_pos--;
            move_user(x, pos, front_pos);
        } else if (op == 3) {
            int pos = split_and_get_pos(x);
            last_answer = tree.query_rank(tree.root, 1, max_pos, pos);

            back_pos++;
            move_user(x, pos, back_pos);
        } else {
            int pos = tree.query_kth(tree.root, 1, max_pos, x);
            last_answer = get_id_by_pos(pos);
        }

        cout << last_answer << '\n';
    }

    return 0;
}

复杂度

令 $V=n+2m$ 。每次区间定位、单点修改、前缀查询和第 $k$ 小都是 $O(\log V)$ ，总时间复杂度为 $O(m\log(n+m))$ 。动态开点路径与区间块总数由操作数控制，空间复杂度为 $O(m\log(n+m))$ 。

解法二：区间节点 FHQ-Treap

思路

这一次不建立绝对坐标，而是直接让 FHQ-Treap 的中序遍历等于当前队列顺序。普通隐式 Treap 的一个节点代表一个用户；这里把连续 ID 区间 $[L,R]$ 打包成一个节点。

节点的大小不是节点数，而是用户数：

sz(u)=sz(left)+sz(right)+(R_u-L_u+1).

初始时整棵树只有节点 $[1,n]$ 。map 保存“区间左端点 $\to$ Treap 节点编号”，于是可以用 upper_bound(x) 找到含有 ID $x$ 的块。

核心操作是按前 $k$ 个用户分裂。若分界正好落在某个区间节点的边界，做普通的子树断开即可；若落在 $[L,R]$ 内部，就把原节点改成左半段，再新建右半段节点，并让右半段继承原节点的优先级。这样树的中序顺序和堆性质都被保留。

由 ID 求排名时，先得到它在所在节点内的偏移和左子树大小；再沿 fa 父指针向根走。每当当前节点是父亲的右儿子，父亲的左子树和父亲自身区间都排在它前面。

要移动或改名，先用两次分裂取出排名为 $k$ 的单点节点 mid。改名后按原顺序合并；置顶合并为 mid + 其余部分；置底合并为 其余部分 + mid。查询第 $k$ 名同样暂时取出 mid，读取其单点 ID 后再合并回去。

正确性

归纳维护以下不变量：Treap 的中序遍历等于当前用户队列；每个节点表示一段连续 ID；sz 等于子树用户总数；map 能定位每个 ID 所在的节点。初始时它们显然成立。

按用户数分裂会把中序序列准确切成前 $k$ 人和其余人；发生节点内部撕裂时，两个新节点恰好覆盖原区间且顺序不变。merge 只连接“左树所有用户在右树之前”的两段序列，故合并后不变量仍成立。于是取出的 mid 正是目标用户，按不同顺序合并就分别完成改名、置顶、置底和第 $k$ 名查询，所有输出正确。

代码

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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283/**
 * 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-16 21:45
 * update_at: 2026-09-16 21:45
 *
 * P3285 [SCOI2014] 方伯伯的OJ
 *
 * 思路：FHQ-Treap 维护“区间节点” + 动态撕裂 + 父指针求排名
 *
 * n 高达 1e8，但操作只有 m <= 1e5 次，绝大多数用户的相对顺序永远不变。
 * 因此把连续的一段用户 [L,R] 打包成一个 Treap 节点（等价类思想）：
 *   - 节点的 size = 左子树 size + 右子树 size + (R - L + 1)
 *   - 初始整棵树只有一个节点 [1, n]
 *
 * map<int,int> mp 记录“每个区间的左端点 -> 该区间所在的 Treap 节点编号”。
 * 想定位用户 x 时：mp.upper_bound(x) 再 --it，就拿到包含 x 的那个区间。
 *
 * 当某次操作需要单独处理区间内部的一个点时，在 split 的递归下放过程中
 * 把这个区间节点“撕成”两个节点，这就是动态撕裂；新节点的优先级继承原节点，
 * 从而保证堆性质不被打乱。
 *
 * 每个节点还要维护父指针 fa，由 ID 反推排名时从节点往上爬：
 * 自己是父亲的右儿子时，父亲的左子树和父亲自身的区间都排在自己前面。
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005; // 初始 1 个节点 + 每次撕裂最多新增 1 个节点

int n, m;
int last_ans; // 上一次操作的输出，即题面中的 a

// ================= FHQ-Treap（区间节点版） =================

int root;                 // 当前树根
int L[MAXN], R[MAXN];     // 每个节点代表的用户编号区间 [L, R]
int ls[MAXN], rs[MAXN];   // 左右儿子
int sz[MAXN];             // 子树内用户总数（不是节点数）
int pri[MAXN];            // 随机优先级，大根堆
int fa[MAXN];             // 父指针，用于由节点反推排名
int tot;                  // 节点池大小

map<int, int> mp; // 区间左端点 -> 节点编号

// 建立编号为 id、代表区间 [l, r] 的新节点。
void new_node(int id, int l, int r) {
    L[id] = l;
    R[id] = r;
    ls[id] = rs[id] = fa[id] = 0;
    sz[id] = r - l + 1;
    pri[id] = rand();
}

// 用左右儿子信息更新自己的 size。
void push_up(int u) {
    sz[u] = sz[ls[u]] + sz[rs[u]] + (R[u] - L[u] + 1);
    // 同步父指针，保证爬树求排名时不会走错
    if (ls[u]) fa[ls[u]] = u;
    if (rs[u]) fa[rs[u]] = u;
}

/**
 * 按“用户数量”分裂：把树 u 切成 x（前 k 个用户）和 y（其余用户）。
 *
 * 与普通 FHQ-Treap 的区别：第 k 个用户可能落在某个区间节点 a 的内部，
 * 这时必须把这个节点撕成 [L,L+k-1] 和 [L+k,R] 两个节点。
 */
void split(int u, int k, int &x, int &y) {
    if (u == 0) {
        x = y = 0;
        return;
    }

    int left_sz = sz[ls[u]];      // 左子树里的用户数
    int len = R[u] - L[u] + 1;    // 自己这个区间的长度

    if (k < left_sz) {
        // 分界点在左子树内部，继续往左递归
        y = u;
        split(ls[u], k, x, ls[u]);
        push_up(y);
    } else if (k > left_sz + len) {
        // 分界点在右子树内部，继续往右递归
        x = u;
        split(rs[u], k - left_sz - len, rs[u], y);
        push_up(x);
    } else if (k == left_sz) {
        // 分界点刚好落在自己区间的左端之前：直接把左子树切出来
        x = ls[u];
        ls[u] = 0;
        if (x) fa[x] = 0;
        push_up(u);
        y = u;
    } else if (k == left_sz + len) {
        // 分界点刚好落在自己区间的右端之后：直接把右子树切出去
        y = rs[u];
        rs[u] = 0;
        if (y) fa[y] = 0;
        push_up(u);
        x = u;
    } else {
        // 核心：分界点落在这个区间内部，触发动态撕裂
        int kk = k - left_sz; // 这个区间要保留前 kk 个用户
        int v = ++tot;        // 新建节点，装下剩余的用户
        new_node(v, L[u] + kk, R[u]);
        pri[v] = pri[u];      // 继承优先级，保持堆性质

        // 原节点剩下的右子树归新节点，原节点被截断为 [L, L+kk-1]
        rs[v] = rs[u];
        if (rs[v]) fa[rs[v]] = v;
        R[u] = L[u] + kk - 1;
        rs[u] = 0;

        mp[L[v]] = v; // 新区间的左端点登记进 map

        x = u;
        y = v;
        push_up(x);
        push_up(y);
    }
}

// 合并两棵树，要求 x 中所有用户都排在 y 之前。
int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y;

    if (pri[x] > pri[y]) {
        rs[x] = merge(rs[x], y);
        push_up(x);
        return x;
    } else {
        ls[y] = merge(x, ls[y]);
        push_up(y);
        return y;
    }
}

// 分裂后把两棵新根的父指针清空。
void split_root(int k, int &x, int &y) {
    split(root, k, x, y);
    if (x) fa[x] = 0;
    if (y) fa[y] = 0;
}

/**
 * 由用户编号 x 求它当前的绝对排名。
 *
 * mp 里存的是区间左端点，upper_bound(x) 找到第一个左端点大于 x 的区间，
 * 再回退一步就是包含 x 的那个区间。
 */
int get_rank(int x) {
    auto it = mp.upper_bound(x);
    --it;
    int u = it->second;
    int l = it->first;

    // 节点内部的偏移 + 左子树的人数
    int rank = sz[ls[u]] + (x - l + 1);

    // 沿父指针往上爬：自己是右儿子时，父亲整体都在自己前面
    while (fa[u] != 0) {
        int p = fa[u];
        if (rs[p] == u) {
            rank += sz[ls[p]] + (R[p] - L[p] + 1);
        }
        u = p;
    }
    return rank;
}

/**
 * 把当前排名为 k 的那个用户单独切出来。
 * 返回 x（它前面的人）、mid（只有这一个用户）、y（它后面的人）。
 * 因为 split 带动态撕裂，mid 保证是一个长度为 1 的节点。
 */
void cut_one(int k, int &x, int &mid, int &y) {
    int t1, t2;
    split_root(k - 1, x, t1);
    split(t1, 1, mid, y);
    if (mid) fa[mid] = 0;
    if (y) fa[y] = 0;
}

// ================= 主流程 =================

void solve() {
    // 初始只有一个区间节点 [1, n]
    tot = 1;
    new_node(1, 1, n);
    mp[1] = 1;
    root = 1;
    fa[root] = 0;

    // 哨兵：保证 upper_bound(x) 一定能 --it（x = n 时也安全）
    mp[n + 1] = 0;

    last_ans = 0;

    for (int i = 1; i <= m; i++) {
        int opt;
        cin >> opt;

        if (opt == 1) {
            int x, y;
            cin >> x >> y;
            x -= last_ans;
            y -= last_ans;

            int rank = get_rank(x);

            int t1, mid, t2;
            cut_one(rank, t1, mid, t2);

            // 排名不变，只把编号从 x 改成 y
            mp.erase(L[mid]);
            L[mid] = R[mid] = y;
            mp[y] = mid;

            root = merge(merge(t1, mid), t2);

            last_ans = rank;
            cout << rank << "\n";
        } else if (opt == 2) {
            int x;
            cin >> x;
            x -= last_ans;

            int rank = get_rank(x);

            int t1, mid, t2;
            cut_one(rank, t1, mid, t2);

            // 放到最前面
            root = merge(mid, merge(t1, t2));

            last_ans = rank;
            cout << rank << "\n";
        } else if (opt == 3) {
            int x;
            cin >> x;
            x -= last_ans;

            int rank = get_rank(x);

            int t1, mid, t2;
            cut_one(rank, t1, mid, t2);

            // 放到最后面
            root = merge(merge(t1, t2), mid);

            last_ans = rank;
            cout << rank << "\n";
        } else {
            int k;
            cin >> k;
            k -= last_ans;

            int t1, mid, t2;
            cut_one(k, t1, mid, t2);

            // mid 是长度 1 的区间，它的左端点就是答案
            int ans = L[mid];

            root = merge(merge(t1, mid), t2);

            last_ans = ans;
            cout << ans << "\n";
        }
    }
}

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

    srand(233); // 固定种子，方便本地对拍复现
    cin >> n >> m;
    solve();

    return 0;
}

复杂度

每次撕裂最多增加一个区间节点，因此节点数为 $O(m)$ 。随机优先级下，分裂、合并和沿父指针求排名的期望复杂度均为 $O(\log m)$ ；每次操作期望 $O(\log m)$ ，空间复杂度 $O(m)$ 。

复杂度对比

解法	单次操作	空间	实现特点
动态开点线段树	$O(\log(n+m))$	$O(m\log(n+m))$	排名是前缀和，需维护双向 `map`
FHQ-Treap	期望 $O(\log m)$	$O(m)$	直接维护序列，需维护分裂、合并与父指针

两种做法都利用了同一件事：只有少数用户会脱离初始的连续块。偏好绝对坐标和顺序统计时选线段树；熟悉隐式 Treap 的分裂合并时选 FHQ-Treap。

总结

面对 $n$ 很大而操作很少的序列，先寻找“绝大多数元素仍保持连续关系”的块。这里把块内 ID 到位置的对应压缩成一个偏移量，触及单个用户时再细化区间块。

在线段树解法中，这个压缩双射把 ID 查询和坐标顺序统计解耦；在 FHQ-Treap 解法中，它把多个用户合并为一个可按人数分裂的节点。两种数据结构不同，但“连续块 + 动态撕裂”才是共同的核心观察。