Exported on: 9/16/2026, 9:41:46 PM

User — Sep 16, 2026 9:25 PM

P3285 [SCOI2014] 方伯伯的OJ

题目描述

方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。OJ 上注册了 $n$ 个用户，编号为 $1\sim n$，一开始他们按照编号排名。

方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：

1. 操作格式为 $1\ \ x\ \ y$，意味着将编号为 $x$ 的用户编号改为 $y$，而排名不变，执行完该操作后需要输出该用户在队列中的位置，数据保证 $x$ 必然出现在队列中，同时，$y$ 是一个当前不在排名中的编号。
2. 操作格式为 $2\ \ x$，意味着将编号为 $x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。
3. 操作格式为 $3\ \ x$，意味着将编号为 $x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $x$ 用户的排名。
4. 操作格式为 $4\ \ k$，意味着查询当前排名为 $k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。

但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：

• $1\ \ x+a\ \ y+a$；
• $2\ \ x+a$；
• $3\ \ x+a$；
• $4\ \ k+a$；
• 其中 $a$ 为上一次操作得到的输出，一开始 $a=0$。

例如：上一次操作得到的输出是 $5$，这一次操作的输入为：$1\ \ 13\ \ 15$ 因为这个输入是经过加密后的，所以你应该处理的操作是 $1\ \ 8\ \ 10$。

现在你截获了方伯伯的所有操作，希望你能给出结果。

输入格式

输入的第 $1$ 行包含 $2$ 个用空格分隔的整数 $n$ 和 $m$，表示初始用户数和操作数。此后有 $m$ 行，每行是一个询问，询问格式如上所示。

输出格式

输出包含 $m$ 行。每行包含一个整数，其中第 $i$ 行的整数表示第 $i$ 个操作的输出。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
1110 10
1 2 11
3 13
2 5
3 7
2 8
2 10
2 11
3 14
2 18
4 9

输出 #1

1
2
3
4
5
6
7
8
9
102
2
2
4
3
5
5
7
8
11

说明/提示

对于 $100\%$ 的数据，$1 \le n \le 10^8$，$1 \le m \le 10^5$。

输入保证对于所有的操作 $1,2,3$，$x$ 必然已经出现在队列中，同时对于所有操作 $1$，$1 \le y \le 2\times 10^8$，并且 $y$ 没有出现在队列中。

对于所有操作 $4$，保证 $1 \le k \le n$。

怎么使用fhq-treap 解这个题目, 一步一步的思考

Gemini — Sep 16, 2026 9:25 PM

你好！我是你的算法教练。这道《方伯伯的OJ》是非常经典的平衡树进阶题目。

题目最大的难点在于 $n \le 10^8$ 的数据范围。如果给每个用户建一个节点，空间会瞬间爆炸。但同时注意到操作次数 $m \le 10^5$，这意味着绝大多数用户的相对顺序是永远不会改变的。

结合你掌握的离散数学知识，我们可以用等价类与集合的划分 (Partition of a Set) 来理解：初始时，所有用户同属一个大集合 $[1, n]$。当我们要单独操作某个用户 $x$ 时，就是对这个集合进行“细分” (Refinement) —— 将其拆解为 $[1, x-1]$、$x$、$[x+1, n]$ 三个新的子集。

在数据结构上，我们用 FHQ-Treap 的一个节点来维护这样一个“连续的子集”（即区间）。接下来，我们一步一步拆解这道题的破局思维。

第一步：引入“区间节点”与 Map 映射

我们让 FHQ-Treap 的每个节点代表一个连续区间 $[L, R]$。

• 节点的 size = 左子树的总大小 + 右子树的总大小 + $(R - L + 1)$。
• 初始时，整棵树只有一个节点，代表区间 $[1, n]$。
• 为了能根据用户 ID 快速找到他所在的节点，我们维护一个 std::map<int, int> mp，键为区间的左端点 $L$，值为该区间在 Treap 中的节点编号。查询 ID=$x$ 时，只需 mp.upper_bound(x) 并向前退一步，就能找到包含 $x$ 的区间。

第二步：动态撕裂——改造 FHQ-Treap 的 Split

在普通的 FHQ-Treap 中，我们按大小分裂树 split(root, K, x, y)。但现在，我们要分裂的第 $K$ 个元素可能隐藏在某个区间节点的内部！ 所以我们需要在 split 的下放过程中，加入**“动态撕裂节点”**的逻辑：

当发现需要的元素数量 $K$ 刚好落在当前节点 now 的区间内部时：

1. 我们将原本的 $[L, R]$ 拆成左右两部分：原节点 now 保留前 $k$ 个元素，变为 $[L, L+k-1]$；
2. 新建一个节点 v 存放剩下的元素，区间为 $[L+k, R]$；
3. 将 v 记录进 map 中；
4. 为了完美维持 Treap 的堆性质，我们直接令 val[v] = val[now]。
5. 此时 x = now, y = v，直接完成了整棵树在这个位置的精准断裂！

第三步：如何利用 parent 指针求 Rank？

FHQ-Treap 默认不带父节点指针，但为了满足这道题“由 ID 查 Rank”的需求，我们必须维护一个 fa 数组。 当我们通过 map 找到元素 $x$ 所在的节点 node 时：

1. 它的初始排名是：左子树大小 + (x - L + 1)。
2. 顺着 fa 指针一路向上爬到根节点：每次发现自己是父亲的右儿子时，说明父亲节点本身、以及父亲的左子树，全都排在自己前面。此时将排名累加上：父亲的左子树大小 + 父亲区间的长度。

第四步：四种操作的优雅转化

有了上面三个核心机制，题目要求的四种操作就变成了单纯的组合积木：

• 提取操作：无论是哪种操作，只要找到目标，我们都用 split 将树切三刀，变成 $T_1$ (目标前)、$mid$ (目标自己, 长度绝对为1)、$T_2$ (目标后)。
• 操作 1 (改ID)：将 $mid$ 的 $L$ 和 $R$ 改成新 ID $y$，并更新 map，原位 merge 回去。
• 操作 2 (置顶)：把 $mid$ 拼到最前面：merge(mid, merge(T1, T2))。
• 操作 3 (置底)：把 $mid$ 拼到最后面：merge(merge(T1, T2), mid)。
• 操作 4 (查ID)：直接按名次分裂出 $mid$ 节点，输出它的 $L$。

核心代码骨架 (C++)

为了让你更直观地理解动态分裂和父节点维护，这是核心的 split 与 merge 实现：

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// 带有动态撕裂功能的按排名分裂
void split(int now, int K, int &x, int &y) {
    if (!now) { x = y = 0; return; }
    int left_elements = sz[ls[now]];
    int len = R[now] - L[now] + 1;
    
    if (K <= left_elements) {
        y = now;
        split(ls[now], K, x, ls[y]);
        if (ls[y]) fa[ls[y]] = y;
        update(y);
    } else if (K >= left_elements + len) {
        x = now;
        split(rs[now], K - left_elements - len, rs[x], y);
        if (rs[x]) fa[rs[x]] = x;
        update(x);
    } else {
        // 核心：K 正好落在当前区间内部！触发节点撕裂
        int k = K - left_elements; 
        int v = ++tot;
        L[v] = L[now] + k; 
        R[v] = R[now];
        val[v] = val[now]; // 继承堆随机值，完美保持堆性质
        
        rs[v] = rs[now]; 
        if (rs[v]) fa[rs[v]] = v;
        ls[v] = 0; fa[v] = 0;
        
        R[now] = L[now] + k - 1; // 截断原节点
        rs[now] = 0; fa[now] = 0;
        
        mp[L[v]] = v; // 将新分裂出的区间加入 map
        
        x = now; y = v; // 直接在此处断开树
        update(v); update(now);
    }
}

// 封装一次 split，确保分离后的根节点父指针为空
void split_wrap(int root, int K, int &x, int &y) {
    split(root, K, x, y);
    if (x) fa[x] = 0;
    if (y) fa[y] = 0;
}

// 维护父指针的 merge
int merge(int x, int y) {
    if (!x || !y) return x | y;
    if (val[x] > val[y]) {
        rs[x] = merge(rs[x], y);
        if (rs[x]) fa[rs[x]] = x;
        update(x);
        return x;
    } else {
        ls[y] = merge(x, ls[y]);
        if (ls[y]) fa[ls[y]] = y;
        update(y);
        return y;
    }
}

📶 信号反射 & 思维模板

• 关键信号 (Key Signals)：
  1. 序列长度极大 ($N \sim 10^8$)，但修改操作极少 ($M \sim 10^5$)。
  2. 需要支持序列元素的“前移/后移/按下标查值/按值查下标”。
• 逻辑跃迁 (Logic Jump)：
  1. 看到操作特征 -> 确定必须使用平衡树（Splay/FHQ-Treap）维护序列。
  2. 看到 $10^8$ 空间限制 -> 联想到离散数学的等价类思想，引入区间节点（Interval Node），只在必要时进行懒分裂（动态撕裂）。
  3. 看到需要“由值找排名” -> 补充 std::map 映射和底层向上的 parent 追溯。
• 模式识别 (Pattern Recognition)： 以后看到 “超大范围序列 + 极少量位移操作 + 排名双向查询”，本能反应就应该是 “包含父指针的 FHQ-Treap + 动态区间节点撕裂 + Map 映射查找” 模型。

User — Sep 16, 2026 9:37 PM

所以 map 里面记录的是 id 对应的 fhq-treap 节点的编号 ?

Gemini — Sep 16, 2026 9:37 PM

是的，但不仅限于单个 ID。更准确地说，map 里面记录的是**“每个连续区间的左端点 ID”**对应的 FHQ-Treap 节点编号。

因为题目中 $n$ 高达 $10^8$，我们绝对不可能把每一个用户 ID 都存进 map 里，那样空间会瞬间爆炸。这正是离散数学中利用“等价类代表元”的思想：我们用区间的左端点 $L$ 来代表这一整个区间的元素。

Map 的具体工作机制

在我们的设计中，FHQ-Treap 的一个节点存的是一个区间 $[L, R]$，那么我们在 map 中记录的就是： mp[L] = 该节点在 Treap 数组中的下标

当你想要查询任意一个用户编号 $x$ 时（比如 $x=5$，而此时它正包含在节点区间 $[3, 7]$ 中），我们这样操作：

1. 寻找后继：调用 mp.upper_bound(x)，这会在 map 中找到第一个左端点严格大于 $x$ 的区间。
2. 回退一步：将得到的迭代器向前退一步（--it），此时迭代器指向的，就必定是包含 $x$ 的那个区间 $[L, R]$ 的左端点 $L$。
3. 获取节点：取出 it->second，这就是 $x$ 所在的 FHQ-Treap 节点编号了！

代码层面的体现就是：

1
2
3auto it = mp.upper_bound(x);
--it; // 退回到包含 x 的那个区间的左端点
int node_id = it->second;

找到节点之后，如果要对 $x$ 进行单点操作（比如修改 ID 或者置顶置底），我们再根据这个信息去 Treap 里面执行“动态撕裂”（把 $[L, R]$ 拆成 $[L, x-1]$、$x$、$[x+1, R]$，并把新的左端点补充进 map 中）。

📶 信号反射 & 思维模板

• 关键信号 (Key Signals)： 需要在极大的值域空间（如 $10^8$）中，维护被零散切割的连续段，并支持给出一个点 $x$，快速定位它所在的连续段。
• 逻辑跃迁 (Logic Jump)： 点对点的映射空间太大 -> 连续的元素性质相同，可以被打包 -> 打包后的区间只需要一个“锚点”就能被检索 -> 使用有序数据结构（BST 或红黑树，C++ 中即 std::map）存储左端点作为锚点。
• 模式识别 (Pattern Recognition)： 以后看到“寻找某个值所在的互不相交的连续区间”，本能反应就应该是“存区间的左端点进有序集合，用 upper_bound(x) 找到后继并回退一步 (--it)”模型。

User — Sep 16, 2026 9:40 PM

你来 告诉我 操作1 2 3 4 ,具体如何使用 map 与 fhq-treap 来联动?

Gemini — Sep 16, 2026 9:40 PM

这四个操作的核心纽带是一个至关重要的前置动作：由 ID 反推当前排名 (GetRank)。

在普通 FHQ-Treap 中，我们只能“由排名查节点”。但有了 map 和 fa（父节点指针）后，我们可以建立一个双向映射：map 负责 $ID \rightarrow 节点编号$，fa 链负责 $节点编号 \rightarrow 排名$。

核心前置动作：GetRank(x) 算法

当我们拿到一个操作目标 $x$ 时，联动过程如下：

1. 查 Map 找节点：使用 map.upper_bound(x) 并回退一步，找到包含 $x$ 的区间节点 $u$，以及它的区间端点 $[L, R]$。
2. 计算节点内初始排名：目标元素在节点 $u$ 的局部排名为 $x - L + 1$，加上左子树大小，即 rank = (x - L + 1) + size[ls[u]]。
3. 沿父指针向上追溯：不断执行 u = fa[u]，直到根节点。在此过程中，只要发现当前节点是它父亲的右儿子，说明父亲节点自身代表的区间，以及父亲的整个左子树，都在目标元素前面。此时令 rank = rank + size[ls[fa[u]]] + (R[fa[u]] - L[fa[u]] + 1)。
4. 最终得到的 rank 就是 $x$ 在全局树中的绝对排名。

有了这个绝对排名 $K$，接下来的四个操作就变成了纯粹的 FHQ-Treap 分裂与合并游戏。

操作 1：修改用户编号 (1 x y)

这个操作要求将 $x$ 的 ID 改为 $y$，位置不变。

1. 定位并分裂：先通过 GetRank(x) 求出 $x$ 的排名 $K$。
2. 提取单点：执行两次分裂，将树切成三块。先按大小 $K-1$ 分裂出 $T_1$ 和 $temp$。再对 $temp$ 按大小 $1$ 分裂出 $mid$ 和 $T_2$。 由于我们加入了动态撕裂机制，$mid$ 此时绝对是一个长度仅为 1 的独立节点，代表区间 $[x, x]$。
3. 记录答案：此时直接输出 $K$。
4. 修改属性：直接修改 $mid$ 节点的属性，令其区间变为 $[y, y]$。
5. 更新 Map：从 map 中删除键 $x$，并插入新的映射 mp[y] = mid。
6. 原位合并：排名不变，所以按原样拼回去：merge(T1, merge(mid, T2))。

操作 2：提升到第一位 (2 x)

这个操作要求将 $x$ 移动到序列最开头。

1. 定位并分裂：同理，计算 $x$ 的排名 $K$，按 $K-1$ 和 $1$ 连续分裂出 $T_1$、$mid$、$T_2$。此时 $mid$ 节点代表 $[x, x]$。
2. 记录答案：输出 $K$。
3. 顶置合并：因为 $x$ 变成了第一名，我们要把 $mid$ 拼在最前面。执行 merge(mid, merge(T1, T2)) 即可，新的树根自动更新。

操作 3：降到最后一位 (3 x)

这个操作要求将 $x$ 移动到序列最末尾。

1. 定位并分裂：计算排名 $K$，连续分裂出 $T_1$、$mid$、$T_2$。
2. 记录答案：输出 $K$。
3. 底置合并：因为 $x$ 变成了最后一名，我们要把 $mid$ 拼在最后面。执行 merge(merge(T1, T2), mid)。

操作 4：查询当前排名第 k 的用户 (4 k)

这个操作不需要使用 map，纯粹是经典的平衡树“由名次查值”。

1. 直接分裂：此时操作目标已经是排名 $K$。直接对整棵树按 $K-1$ 和 $1$ 进行两次分裂，得到 $T_1$、$mid$、$T_2$。
2. 记录答案：在动态撕裂机制的保证下，$mid$ 节点依然是长度为 1 的绝对单点 $[L, L]$（或原本就在边界，首元素为 $L$）。直接输出 $mid$ 节点代表的左端点 $L$。
3. 原位合并：序列顺序未发生改变，执行 merge(T1, merge(mid, T2)) 恢复树形。

📶 信号反射 & 思维模板

• 关键信号 (Key Signals)： 题目中同时出现了“改变某元素的位置”和“查询某元素的当前位置”。
• 逻辑跃迁 (Logic Jump)： 看到同时存在按值操作（1,2,3）和按名次操作（4） -> 必须打通 Value 与 Rank 的双向通道 -> 借助 Map 定位物理节点，借助 Parent 指针计算逻辑名次 -> 将所有按值操作转化为按名次操作 -> 统一使用 $T_1$、$mid$、$T_2$ 的三段式 split 解决。
• 模式识别 (Pattern Recognition)： 以后看到“名次与元素值的动态双向查询”，本能反应就应该是“Map定位 + fa指针爬树求Rank + 按Rank切出三段子树重新拼接”模型。

在处理这四个操作时，我们需要确保父指针 fa 在 split 和 merge 时严格同步更新，你觉得在 FHQ-Treap 的 split 下放过程中，哪一步最容易遗漏对父指针的维护？