# 小Y的线段树：离线删除线段树

这是出题人的离线线段树方案，由 [alternative.cpp](alternative.cpp) 实现。位置 $i$ 在前缀 $[1,r]$ 的最终栈中保留，当且仅当右侧没有不小于它的已读元素；该判据不依赖区间左端点。因此，询问 $[l,r]$ 等于当前前缀栈在这个区间内的元素数。

## 维护存活位置

建立线段树，每个叶子对应一个位置，初始存活数为一、最小值为该位置的数值。内部节点保存两儿子的存活数之和，以及存活元素的最小值。删除叶子后，计数变零，最小值设为大于全部合法值的正无穷。

将询问按右端点排序，逐个将扫描位置推进到当前询问的右端点。加入位置 $r$ 时，删除 $[1,r-1]$ 中所有数值不大于 $a_r$ 的存活位置：

- 若线段树区间起点大于 $r-1$ ，或最小值大于 $a_r$ ，直接返回。
- 到达符合条件的叶子时删除它。
- 其他情况递归处理儿子，再合并计数与最小值。

所有叶子从一开始已建立，未扫描后缀也暂时存活；删除操作限制在前缀，询问又限制在 $[l,r]$ ，所以后缀不会影响结果。处理完 $r$ 后，做普通区间计数查询，并按原询问编号保存答案。

## 正确性与复杂度

扫描后，已读位置中存活的恰是尚未遇到右侧不小于自身值的位置。归纳每次删除操作，正好删除此时失去资格的所有位置，且保留其余位置。因此存活集合与前缀栈相同，区间计数给出正确答案。

每个位置最多删除一次，每次删除所涉及的祖先至多 $O(\log N)$ .没有删除发生的分支在最小值条件处立即剪枝；前缀边界另产生每次至多 $O(\log N)$ 的路径开销。所以所有删除共 $O(N\log N)$ ，不是每次扫描整个树。加上询问排序和区间查询，总时间 $O(N\log N+M\log M+M\log N)$ ，空间 $O(N+M)$ .

该方法覆盖完整范围。首选[分桶单调栈](solution.zh.md)避免线段树删除的对数开销。出题人提供离线线段树思路，GPT-6 完成正确推进边界、删除条件、证明和 C++17 实现。性能见[测量记录](../../../docs/benchmark-R25.json)。