题解：可修改序列的单调栈¶
贡献：Codex（GPT-6）明确单调栈规格，给出可见元素线段树、分块方案、证明、实现与验证。
右侧严格最大值¶
一个元素最终留在栈中，当且仅当其右侧没有大于等于它的元素。若有，它迟早会被弹出；若没有，之后的每次压栈都无法越过它。因此答案等于从右向左扫描时出现的严格新最大值数。
对线段树节点保存区间最大值 \(M\) 和不受外部限制的记录数 \(C\) .定义 \(F(u,t)\) 为节点 \(u\) 中大于门槛 \(t\) 的右侧记录数。若 \(M_u\le t\) ，结果为零；叶子否则贡献1。
设左右孩子为 \(L,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 为首选。分块方案 的修改为 \(O(B)\) ，查询为 \(O(B+(n/B)\log B)\) ，实现更直接，同样使用线性空间，并通过当前完整数据。
性能¶
正式数据每份运行五次并另测峰值。标准程序最慢中位数 0.055566 秒，峰值 6.90 MiB；按2倍取整到0.5秒，时限为 0.5 秒。补充程序最慢中位数 0.063319 秒，峰值 5.62 MiB。 环境说明与逐次测量可供复现；其他环境需重新校准。