# 补充解法

贡献：Codex（GPT-6）给出分块解法、证明、实现与验证。

每块从右向左扫描，保存严格新最大值。保存顺序中的值严格递增。查询时也从右向左处理区间，维护已见最大值 $t$ .完整块中大于 $t$ 的记录恰好是它的全部贡献，可用 `upper_bound` 一次二分得到数量；随后把 $t$ 更新为该块最大值。边角位置逐个处理。修改仅重建所属块。

正确性来自[首选题解](solution.zh.md)中的右侧记录等价性。块内非记录已有更大的或相等的右侧元素，永远不可能在完整查询中保留；块内记录是否保留恰好取决于它是否严格大于块外右侧最大值。按从右到左顺序维护门槛，保证完整块和边角都得到正确贡献。

设块长为 $B$ ，块数为 $K=\lceil n/B\rceil$ .预处理 $O(n)$ ；修改 $O(B)$ ；查询 $O(B+K\log(B+1))$ ；空间 $O(n)$ .程序取 $B=224$ .

[alternative.cpp](alternative.cpp) 的结构更直接，修改和查询的最坏渐进时间高于线段树；它通过当前完整数据。线段树仍是首选。