补充解法¶

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

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

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

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

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