题目回顾

维护一个初始包含 $n$ 个不同整数的集合，支持三种操作：

• 插入元素 $x$（保证 $x$ 不在集合中）
• 删除元素 $x$（保证 $x$ 在集合中）
• 查询 $k$-负载：最小的正整数 $d$，使得 $d, d+1, \dots, d+(k-1)$ 都不在集合中

约束：所有测试用例的 $n$ 总和 $\le 2\cdot 10^5$，$m$ 总和 $\le 2\cdot 10^5$，元素值 $\le 2\cdot 10^6$。

---

问题转化

$k$-负载的定义：最小的 $d$，使得长度为 $k$ 的连续整数区间 $[d, d+k-1]$ 完全不在集合中。

换句话说，我们要找所有不在集合中的连续整数区间，并找到其中长度 $\ge k$ 的区间，取这些区间的左端点的最小值。

设集合为 $S$，则“不在集合中的连续整数区间”就是正整数轴上被 $S$ 分割出的“空段”。例如 $S = \{3,4,6,11\}$，正整数轴上的空段为：

• $[1,2]$（长度 $2$）
• $[5,5]$（长度 $1$）
• $[7,10]$（长度 $4$）
• $[12, +\infty)$（无穷长，可视为长度无穷大）

对于 $k=3$，长度 $\ge 3$ 的空段有 $[7,10]$ 和 $[12,+\infty)$，最小左端点是 $7$，即 $3$-负载。

---

核心思路

1. 维护空段（free segments）

用 std::set<int> M 维护当前集合中的所有元素（有序）。空段可以表示为半开区间 $[l, r)$，其中 $l$ 和 $r$ 都是集合中相邻的元素（或边界 $1$ 和 $+\infty$）：

• 若 $M = \{a_1, a_2, \dots, a_t\}$（已排序），则空段为：
  • $[1, a_1)$
  • $[a_i+1, a_{i+1})$ 对 $i=1..t-1$
  • $[a_t+1, +\infty)$

注意 $[a_t+1, +\infty)$ 是一个无限长的空段，处理时用一个大数 $\text{INF}$ 代替 $+\infty$（例如 $2\cdot 10^6+5$ 足够）。

插入 $x$ 时：

• 找到 $x$ 在 $M$ 中的前驱 $L$ 和后继 $R$。
• 原来的空段 $[L+1, R)$ 被 $x$ 拆分成两个空段：$[L+1, x)$ 和 $[x+1, R)$。
• 删除原空段，插入两个新空段。

删除 $x$ 时：

• 找到 $x$ 在 $M$ 中的前驱 $L$ 和后继 $R$。
• 原来的两个空段 $[L+1, x)$ 和 $[x+1, R)$ 合并成一个空段 $[L+1, R)$。
• 删除这两个空段，插入合并后的空段。

2. 查询 $k$-负载

我们需要在所有空段中，找到长度 $\ge k$ 的那些空段，并输出它们的最小左端点。

空段可以用二元组 $(\text{length}, \text{left})$ 表示。对于无限长空段，长度设为 $\text{INF}$（足够大）。

查询 $k$ 时，等价于在所有长度 $\ge k$ 的空段中，找最小左端点。

---

数据结构设计

用笛卡尔树维护空段

对每个空段 $(\text{len}, l)$ 建立一个节点。节点的键值对为 $(\text{len}, l)$，按键值排序（先按长度升序，长度相同时按左端点升序）。

笛卡尔树性质：节点的优先级（随机）满足堆性质，键值满足 BST 性质。

我们需要快速支持：

• 插入/删除一个节点（对应空段的插入/删除）
• 查询所有键值 $\ge (k, -\infty)$ 的节点中的最小 $l$

节点信息

每个节点存储：

• key：$(\text{len}, l)$
• prior：随机优先级
• minl：子树中所有节点的 $l$ 的最小值

upd(v) 维护 minl = min(v.key.l, minl(lv), minl(rv))。

查询操作

查询 $k$ 时，我们想找到所有长度 $\ge k$ 的节点。

由于键值按 $(\text{len}, l)$ 排序，长度 $\ge k$ 的节点在 BST 中正好对应一个后缀：所有键值 $\ge (k, -1)$ 的节点（因为 $l \ge 1$，用 $-1$ 确保包含所有长度为 $k$ 的节点）。

所以：

1. 用 split(root, (k, -1)) 将树分成两部分：
   • s1：键值 $< (k, -1)$ 的节点（长度 $< k$）
   • s2：键值 $\ge (k, -1)$ 的节点（长度 $\ge k$）
2. 答案 = $\min(\text{集合最大元素}+1,\; \text{s2 的 minl})$
   • 因为无限长空段 $[a_t+1, +\infty)$ 的左端点是 $a_t+1$，需要与有限空段的最小左端点比较。
3. 合并回 root = merge(s1, s2)。

特殊情况：集合为空时，整个正整数轴都是空段，$1$-负载就是 $1$。

---

复杂度分析

• 每个插入/删除操作：$O(\log n)$ 用于在 std::set 中找前驱后继，$O(\log n)$ 用于笛卡尔树的 split/merge/删除。
• 每个查询操作：$O(\log n)$ 用于 split 和 merge。
• 总复杂度：$O((n+m)\log n)$。

---

关键实现细节

1. 边界处理：用 $0$ 表示左边界 $1$ 的前驱，用 $\text{INF}=2\cdot 10^6+5$ 表示右边界无穷大。
2. 无限长空段：在 add_val 和 rem_val 中，当 $R = \text{INF}$ 时，不添加右边界为无穷的空段（实际上它一直存在，但查询时会用 *M.rbegin()+1 兜底）。
3. 内存管理：预分配一个大数组 mem 作为节点池，避免动态内存分配开销。
4. 随机优先级：使用 mt19937 保证树的平衡性期望 $O(\log n)$。

---

示例推导

以样例第一个测试用例的部分操作为例：

初始集合 $\{1,2,5,905,2000000\}$，空段：

• $[3,5)$（长度 $2$）
• $[6,905)$（长度 $899$）
• $[906,2000000)$（长度 $1999095$？注意是到 $2000000$ 之前）
• $[2000001, +\infty)$（无限长）

查询 $k=2$：长度 $\ge 2$ 的空段中最小左端点是 $3$？但答案输出第一个 ? 2 结果是 $2$？实际上集合中 $1$ 和 $2$ 存在，所以 $[1,2]$ 不是空段，最小长度 $\ge 2$ 的空段左端点是 $3$ 吗？再检查：$[3,5)$ 左端点是 $3$，但 $[1,2]$ 被占用了，所以 $d=1$ 时 $[1,2]$ 有 $1$ 在集合中，不行；$d=2$ 时 $[2,3]$ 有 $2$ 在集合中，也不行；$d=3$ 时 $[3,4]$ 两个都不在集合中？$3$ 和 $4$ 都不在，确实 $k=2$ 的负载是 $3$？但样例输出第一个 ? 2 是 $2$！说明我理解有误。

重新理解：样例第一个测试用例在第一个 ? 2 之前执行了 - 2，删除 $2$ 后集合为 $\{1,5,905,2000000\}$。空段：

• $[2,5)$：包含 $2,3,4$，长度 $3$，左端点 $2$。
• $[6,905)$，$[906,2000000)$，$[2000001,+\infty)$。

$k=2$：长度 $\ge 2$ 的空段中最小左端点是 $2$。所以答案是 $2$。正确。

---

总结

本题的核心是将 $k$-负载问题转化为“找长度 $\ge k$ 的空段的最小左端点”。使用：

• std::set 维护集合元素，用于快速定位空段边界。
• 笛卡尔树（Treap）维护空段，按长度排序，支持 $O(\log n)$ 的插入、删除、后缀最小值查询。

这种方法巧妙地利用了笛卡尔树的 split 操作，将“长度 $\ge k$”的条件转化为树上的后缀分割，从而高效地回答查询。