# 题解：可修改序列的单调栈

贡献：Codex（GPT-6）明确单调栈规格，给出可见元素线段树、分块方案、证明、实现与验证。

## 右侧严格最大值

一个元素最终留在栈中，当且仅当其右侧没有大于等于它的元素。若有，它迟早会被弹出；若没有，之后的每次压栈都无法越过它。因此答案等于从右向左扫描时出现的严格新最大值数。

对线段树节点保存区间最大值 $M$ 和不受外部限制的记录数 $C$ .定义 $F(u,t)$ 为节点 $u$ 中大于门槛 $t$ 的右侧记录数。若 $M_u\le t$ ，结果为零；叶子否则贡献1。

设左右孩子为 $L,R$ .右区间先扫描，左区间贡献为 $F(L,M_R)$ ，所以

$$C_u=C_R+F(L,M_R).$$

计算 $F(u,t)$ 时有两种情况：

- $M_R\le t$ ：右侧全被挡住，递归计算 $F(L,t)$ .
- $M_R>t$ ：右侧的最大值一定被保留，它使左侧门槛固定为 $M_R$ .左侧贡献已经存在于 $C_u-C_R$ 中，只递归计算 $F(R,t)$ .

每层只进入一个孩子，故一次 $F$ 查询用 $O(\log n)$ 时间。

## 修改和区间查询

单点修改后，自底向上重算 $M,C$ .每次合并调用一次 $F$ ，共 $O(\log^2 n)$ .

区间查询将覆盖节点按**从右到左**的顺序处理。门槛初始为 $-1$ ，表示此前尚无元素。处理完整节点时，把 $F(u,t)$ 加入答案，再令 $t=\max(t,M_u)$ .它准确模拟右侧已扫描部分给当前节点的限制。覆盖节点数为 $O(\log n)$ ，总查询时间也是 $O(\log^2 n)$ .

上述记录等价性、合并恒等式和门槛不变量共同证明每次查询得到规定单调栈的大小。相等值必须挡住左侧元素，所有比较均与严格记录一致。

## 复杂度与方案选择

设 $n$ 为序列长度，$m$ 为操作数。建树的每个高度 $h$ 节点至多做 $O(h)$ 工作，而该高度只有 $O(n/2^h)$ 个节点，故建树总计 $O(n)$ .每次修改或查询 $O(\log^2 n)$ ，总空间 $O(n)$ .

[std.cpp](std.cpp) 为首选。[分块方案](solution-alternative.zh.md) 的修改为 $O(B)$ ，查询为 $O(B+(n/B)\log B)$ ，实现更直接，同样使用线性空间，并通过当前完整数据。

## 性能

正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.055566 秒，峰值 6.90 MiB；按2倍取整到0.5秒，时限为 0.5 秒。补充程序最慢中位数 0.063319 秒，峰值 5.62 MiB。 [环境说明](../../../docs/评测环境与性能.md)与[逐次测量](../../../docs/benchmark-R34.json)可供复现；其他环境需重新校准。