Exported on: 9/15/2026, 10:14:39 PM

User — Sep 15, 2026 6:44 PM

P1503 鬼子进村

题目背景

小卡正在新家的客厅中看电视。电视里正在播放放了千八百次依旧重播的《亮剑》，剧中李云龙带领的独立团在一个县城遇到了一个鬼子小队，于是独立团与鬼子展开游击战。

题目描述

县城里有 $n$ 个用地道相连的房子，第 $i$ 个只与第 $i-1$ 和第 $i+1$ 个相连。特别的，第 $1$ 个房子只和第 $2$ 个联通，第 $n$ 个房子只和第 $n-1$ 个联通。这时有 $m$ 个消息依次传来：

1. 若消息为 D x：鬼子将 $x$ 号房子摧毁了，地道被堵上。

2. 若消息为 R ：村民们将鬼子上一个摧毁的房子修复了。

3. 若消息为 Q x：有一名士兵被围堵在 $x$ 号房子中。

现定义能够到达如下：若存在房子 $i,j(1\leq i\leq j\leq n)$，使得对于任意的 $k(i\leq k\leq j)$ 都满足房子 $k$ 未被摧毁，则称房子 $i$ 与房子 $j$ 互相能够到达。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

输入格式

第一行两个整数 $n,m$。

接下来 $m$ 行，有如题目所说的三种信息共 $m$ 条。

输出格式

对于每一个被围堵的士兵，输出该士兵能够到达的房子数。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
10
117 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

输出 #1

1
2
3
4
51
0
2
4

说明/提示

$1\leq n,m\leq 5\times 10^4$。

若士兵被围堵在摧毁了的房子中，那只能等死了。。。。。。

这个题目用来求i 之前的最近的 元素(摧毁) 的编号, 和 之后的最近元素 我说的对吗 ?

Gemini — Sep 15, 2026 6:44 PM

你的直觉非常敏锐，完全正确！这道题的核心本质恰好就是寻找元素 $x$ 左右两侧最近的被摧毁的房子。

我们可以用离散数学的集合与偏序关系来形式化地拆解你的直觉：

设全集为所有房子的编号 $U = \{1, 2, ..., n\}$。为了处理边界情况，我们定义虚拟边界 0 和 n+1，并认为它们默认处于“始终被摧毁”的状态。 设当前所有被摧毁的房子的集合为 $S$（注意 $0 \in S$ 且 $n+1 \in S$）。

对于任意一次查询 $x$：

1. 属于关系判定：如果 $x \in S$，说明房子本身已被摧毁，它所在的连通块大小必定为 0。
2. 极值查找：如果 $x \notin S$，我们需要在偏序集 $(S, \le)$ 中寻找 $x$ 的前驱和后继：
   • 左侧最近的摧毁点 $L = \max\{y \mid y \in S \land y < x\}$
   • 右侧最近的摧毁点 $R = \min\{y \mid y \in S \land y > x\}$

此时，$x$ 所在的极大连通子图就是开区间 $(L, R)$ 内的所有整数点。由于是离散的整数序列，这个连通块包含的元素个数非常明确，即为：

从数据结构落地的角度来看，C++ 标准库中的 std::set（底层为红黑树）是维护动态有序集合 $S$ 最理想的工具：

• 摧毁（D）：set.insert(x)
• 查找右边界 $R$：利用 set.upper_bound(x)，时间复杂度为 $\mathcal{O}(\log n)$。
• 查找左边界 $L$：找到 $R$ 的迭代器后，向前自减一次（--it）即可得到 $L$。
• 修复（R）：因为题目说明是修复“上一个摧毁的房子”，这呈现完美的“后进先出”（LIFO）逻辑，配合一个 std::stack 来记录销毁历史即可轻松实现撤销。

📶 信号反射 & 思维模板

1. 关键信号 (Key Signals)：

   • 信号 1：“在一维连续序列上破坏元素，查询某点所在的连通块大小” —— 暗示区间被断点割裂。
   • 信号 2：“修复上一个被破坏的房子” —— 强暗示 LIFO 结构（栈）。
   • 信号 3：数据范围 $n, m \le 5\times 10^4$ —— 要求单次查询和修改的时间复杂度必须在 $\mathcal{O}(\log n)$ 级别。

2. 逻辑跃迁 (Logic Jump)：

   • 看到“求连续未被破坏的区间长度”，跳跃到 $\rightarrow$ “连通块长度 = 右侧最近断点 - 左侧最近断点 - 1”。
   • 看到“动态添加/删除断点且需要查找邻接点”，跳跃到 $\rightarrow$ “维护一个有序集合，并利用二分查找快速定位前驱和后继”。

3. 模式识别 (Pattern Recognition)：

   • 以后看到“一维序列的动态断点维护 + 连通块查询”，本能反应就应该是“std::set 维护断点 + upper_bound 找区间”。

User — Sep 15, 2026 10:13 PM

所以如果使用fhq-treap 来完成这个题目, 就是把fhq-treap 当成 set来使用, 然后按key 来分裂, 求出tree l的最大值 tree r 的最小值 对吗 ? 如果是静态的 : 不修改的,就可以使用二分查找对吗?

Gemini — Sep 15, 2026 10:13 PM

完全正确！ 你的思路非常清晰，这两点思考都精准切中了数据结构与算法的本质。

无论是使用 FHQ-Treap 还是二分查找，其底层的数学本质都是在全序集 (Total Order Set) 中寻找元素的前驱 (Predecessor) 和后继 (Successor)。我们来详细拆解你的两个绝佳思路：

1. 使用 FHQ-Treap 替代 set (动态前驱/后继模型)

把 FHQ-Treap 当作平衡二叉搜索树（BST）版本的 set 来使用，这个思路完全可行，并且在教学上是一个极好的切入点，能帮助学生彻底理解 set 的底层机制。

具体操作逻辑如下：

• 分裂 (Split)：对于查询点 $x$，我们按关键字（房屋编号）将整棵 FHQ-Treap 分裂为两棵树。
  • 执行 split(root, x, tree_l, tree_r)。
  • 由于查询时已知 $x$ 没被摧毁（若 $x$ 已摧毁直接输出 0 即可，可用一个布尔数组 O(1) 判断），那么 tree_l 中全都是 $< x$ 的被摧毁房屋，tree_r 中全都是 $> x$ 的被摧毁房屋。
• 求极值 (Find Extremes)：
  • 左侧最近被摧毁房屋 ($L$)：即 tree_l 中的最大值。在二叉搜索树中，最大值就是最右侧的叶子节点（一路向右儿子走到底：while(node->rc) node = node->rc;）。
  • 右侧最近被摧毁房屋 ($R$)：即 tree_r 中的最小值。在二叉搜索树中，最小值就是最左侧的叶子节点（一路向左儿子走到底：while(node->lc) node = node->lc;）。
• 合并 (Merge)：查询结束后，执行 root = merge(tree_l, tree_r) 将树无损还原。
• 插入与撤销 (Insert / Undo)：摧毁房屋就是标准的 FHQ-Treap 插入节点操作；撤销（修复）可以通过栈记录历史，弹出栈顶元素并在 FHQ-Treap 中执行删除节点操作。

这样做的时间复杂度同样严格保证在 $\mathcal{O}(\log n)$，且常数在可接受范围内。

2. 如果题目是静态的 (静态前驱/后继模型)

你的推论也是绝对正确的。如果题目中没有修改操作（即所有 D 操作都在一开始给出，后续全是 Q 查询），那么动态的数据结构（红黑树、FHQ-Treap、线段树）就显得“杀鸡用牛刀”了。

在离散数学中，静态集的关系一旦确立就不再改变。我们可以直接退化为最朴素的线性结构：

1. 预处理：将所有被摧毁的房子编号放入一个数组（或者 std::vector）中。
2. 加入边界：把 $0$ 和 $n+1$ 也放进数组，防止越界。
3. 排序：使用 std::sort 对数组进行升序排序，使其成为一个严格递增的序列。
4. 二分查找：对于任何查询 $x$：
   • 求右边界 $R$：直接调用 std::upper_bound 查找第一个大于 $x$ 的元素。
   • 求左边界 $L$：找到 $R$ 的迭代器（或指针）后，向前偏移一个单位（*(it - 1)）即为 $L$。

整个查询过程也是单次 $\mathcal{O}(\log n)$，但由于数组的内存连续性，静态二分查找的常数和缓存命中率（Cache Hit Rate）会远远优于任何树形结构。

📶 信号反射 & 思维模板

1. 关键信号 (Key Signals)：

   • 信号 1：“按值分裂”或“查找动态集合中的最大/最小值” —— 暗示 FHQ-Treap 的树形极值性质（最左/最右节点）。
   • 信号 2：“题目只有查询，没有或者修改可以离线预处理” —— 暗示“动态问题静态化”。

2. 逻辑跃迁 (Logic Jump)：

   • 看到“动态集合查找前驱后继”，跳跃到 $\rightarrow$ “FHQ-Treap 按 $x$ 划分树，左树找最右，右树找最左”。
   • 看到“去除修改操作（变静态）”，跳跃到 $\rightarrow$ “二叉树退化为一维有序数组，树上搜索退化为数组上的二分查找（lower_bound/upper_bound）”。

3. 模式识别 (Pattern Recognition)：

   • 以后看到“动态前驱/后继维护”，本能反应就应该是“set 或 FHQ-Treap 分裂取极值”；
   • 以后看到“静态区间查询 / 无修改的前驱后继”，本能反应就应该是“排序数组 + 二分查找，能不用数据结构就坚决不用数据结构”。