题解

思路

考虑区间 $[l,r]$，假设已经通过横向操作统一删除了 $base$ 层。设区间最小值为 $m$。可以直接对每个位置使用一次单点操作，代价 $r-l+1$；也可以再做 $m-base$ 次整段横向操作，然后递归处理所有大于 $m$ 的连续子段。

做法

递归函数返回上述两种方案的较小值。直接扫描区间找最小值并划分子段即可；$n\le5000$ 时最坏 $O(n^2)$ 足够。独立 Oracle 用线段树查询最小值下标，使分治为 $O(n\log n)$。

短小层使用状态 BFS 穷举所有合法减一区间及单点清零操作。二进制层中每个连续的 1 段一次横向操作即可清空，答案就是 1 段数量。

正确性证明

最优方案若不用跨越整个当前区间的横向操作，只能分别清除各位置，代价不会优于逐点各一次。否则所有跨越整个区间的横向操作最多做到最小值 $m$，先执行恰好 $m-base$ 次不会妨碍任何其他操作；达到这一层后值等于 $m$ 的位置把问题唯一分成互不影响的正子段。两种情况覆盖全部最优方案，递归取最小故正确。

复杂度

标程时间复杂度 $O(n^2)$，递归空间复杂度 $O(n)$。