题目理解

我们有一个长度为 $N$ 的数组 $a$，值域 $[1, N]$。
有两种操作：

1. F c h：在所有 $a[i] \ge h$ 的元素中，选出最小的 $c$ 个数，将它们 $+1$。
2. C min max：查询值在 $[\min, \max]$ 范围内的元素个数。

$N, M \le 10^5$。

难点分析

F 操作比较特殊：

• 先按值筛选（$a[i] \ge h$）
• 再按值排序（取最小的 $c$ 个）
• 然后给它们 $+1$

这会导致值的变化，而且可能破坏平衡树中的有序性（因为加 1 后可能大于后面的某些元素）。

解题思路

1. 数据结构选择

我们需要支持：

• 按值分裂、合并
• 区间加
• 查询排名

这里使用 无旋 Treap（FHQ Treap），因为它天然支持按值分裂和合并。

2. 核心难点：F c h 操作

假设我们要执行 F c h：

1. 按 $h$ 分裂：
   split(rt, h-1, rtl, rtr)
   这样 rtr 中所有节点的值 $\ge h$。

2. 在 rtr 中取最小的 $c$ 个：
   split_siz(rtr, min(c, tr[rtr].siz), rtx, rtr2)
rtx 就是我们要加 1 的那部分节点。

3. 整体加 1：
   change(rtx, 1)（打标记）

4. 问题出现：
   加 1 后，rtx 中最大值可能等于 rtr2 中最小值，甚至大于？
   不对，因为 rtx 是 rtr 中最小的 $c$ 个，rtr2 是剩下的（更大的），加 1 后 rtx 的最大值最多等于 rtr2 的最小值，不会大于。
   但是可能等于，这样有序性仍然保持吗？
   实际上，如果 rtx 的最大值等于 rtr2 的最小值，那么它们值相等，但 Treap 里允许相等值任意排列，所以合并时没问题。

   但是，如果 rtx 的最大值加 1 后大于 rtr2 的最小值呢？
   这是可能的！例如：

   • rtr 的值: [3, 4, 5]
   • c=2 → rtx=[3,4], rtr2=[5]
   • 加 1 后 rtx=[4,5], rtr2=[5]
     这时 rtx 的最大值 5 等于 rtr2 的最小值 5，没问题。

   但是考虑：

   • rtr 的值: [5,5,6]
   • c=2 → rtx=[5,5], rtr2=[6]
   • 加 1 后 rtx=[6,6], rtr2=[6]
     还是相等。

   再考虑：

   • rtr 的值: [5,6,7]
   • c=2 → rtx=[5,6], rtr2=[7]
   • 加 1 后 rtx=[6,7], rtr2=[7]
     仍然 rtx 的最大值 ≤ rtr2 的最小值。

   结论：rtx 的最大值加 1 后不会大于 rtr2 的最小值，因为 rtr2 的最小值原本就大于等于 rtx 的最大值，加 1 后最多相等。

   所以有序性仍然保持，可以直接合并回去。

   但是代码中为什么还要再按 mx 分裂呢？

   看代码：

   int mx = tr[rtx].mx;
   change(rtx, 1);
   split(rtx, mx, r1, r2);
   split(rtr, mx, r3, r4);
   rt = merge(rtl, merge(merge(r1, r3), merge(r2, r4)));
   

   这里 mx 是加 1 前的最大值，加 1 后 rtx 中值 $\le mx$ 的部分是哪些？
   实际上，rtx 中原本所有值 $\le mx$，加 1 后，原本值等于 mx 的现在变成 mx+1，原本小于 mx 的现在 $\le mx$。
   所以 split(rtx, mx) 会把加 1 后值 $\le mx$ 的分到 r1，值 $= mx+1$ 的分到 r2。

   同理，split(rtr, mx) 把 rtr 中值 $\le mx$ 的分到 r3，值 $> mx$ 的分到 r4。

   然后合并顺序：r1, r3, r2, r4
   为什么这样合并？

   • r1（来自 rtx，值 $\le mx$）
   • r3（来自 rtr，值 $\le mx$）
     这两部分值范围相同，合并时顺序任意（Treap 按优先级）。
   • 然后合并 r2（来自 rtx，值 $= mx+1$）
   • 最后 r4（来自 rtr，值 $> mx$）

   这样保证了整体有序。

   其实这里是为了处理 rtx 和 rtr 中可能存在相同值的情况，让相同值的节点均匀合并，避免退化。

代码流程

初始化

• 读入数组 a，排序（因为初始 Treap 要有序）
• 依次插入 Treap

操作处理

C min max

• 利用 get_siz(max) - get_siz(min-1) 得到排名差，即区间内个数。

F c h

1. 按 $h-1$ 分裂，得到 $\ge h$ 的部分 rtr。
2. 在 rtr 中取前 $c$ 个（最小的 $c$ 个）rtx。
3. 记录 mx = tr[rtx].mx。
4. 整体加 1。
5. 把 rtx 按 mx 分裂成 r1（值 $\le mx$）和 r2（值 $= mx+1$）。
6. 把 rtr 剩余部分按 mx 分裂成 r3（值 $\le mx$）和 r4（值 $> mx$）。
7. 合并：rtl + (r1 + r3) + (r2 + r4)。

复杂度

• 每次操作 $O(\log N)$
• 总复杂度 $O((N+M)\log N)$

样例验证

以题目样例：

初始：[1, 3, 2, 5, 2] 排序 → [1, 2, 2, 3, 5]

1. F 2 1：
   $\ge 1$ 的全部中最小 2 个是 [1, 2] → 加 1 后 [2, 3, 2, 3, 5]（排序 [2, 2, 3, 3, 5]）

2. C 3 6：
   值在 [3,6] 的有 3,3,5 → 输出 3

3. F 2 3：
   $\ge 3$ 的有 [3,3,5]，最小 2 个是 [3,3] → 加 1 后 [2, 2, 4, 4, 5]

4. C 6 8：
   没有值在 [6,8] → 输出 0

5. F 2 1：
   $\ge 1$ 的全部中最小 2 个是 [2,2] → 加 1 后 [3, 3, 4, 4, 5]

6. F 2 2：
   $\ge 2$ 的有 [3,3,4,4,5]，最小 2 个是 [3,3] → 加 1 后 [4,4,4,4,5]

7. C 3 5：
   值在 [3,5] 的有 4,4,4,4,5 → 输出 5

与题目输出一致。

总结

这道题的关键在于：

1. 使用 FHQ Treap 维护有序序列
2. F 操作时通过分裂取出要修改的部分
3. 修改后通过按原最大值再次分裂，保证合并时有序性
4. 查询时用排名差求区间个数

这种“按值分裂 → 按大小取子集 → 修改 → 再分裂 → 合并”的思路，是处理这类动态有序序列修改问题的经典方法。