题解：P11288 [COTS 2017] 模板 Z1

· · 题解

[COTS 2017] 模板 Z1

以前见过类似套路的题然而不会做了。。。还是太菜了。

这种涉及到区间 min/max 的数数题首先考虑简化成只有 0 和 1 的情况（即 h=2），且保证限制的 x=1。此时有个很显然的 dp，设 f_{i,j} 表示前 i 个位置，上一个为 1 的位置在 j，转移时考虑 i 这一位放不放 1，直接转移即可，时间复杂度 \operatorname{O}(n^2)。

这个复杂度显然是不能接受的，考虑进行优化。发现转移的时候是实际上是要将 j 为一段前缀的状态清成 0（因为这些位置不满足区间内一定要有 1 的限制），然后对于一个前缀求和，对 f_{i,i} 单点更改，可以用线段树维护整体 dp 做到 \operatorname{O}(n\log n)。

（如果不会上面这一段可以先去学一下 Intervals，或者可以根据下面那个写的比较详细的 dp 脑部一下）。

接着考虑这道题本身的做法。首先可以快速维护出每一个位置可以取到的上界，那么我们可以观察到一个性质：对于一个限制 (l,r,x)，所有满足 i\in [l,r], a_i=x 的 i 可填到的上界一定为 x。

考虑证明上面这个事情。对于上界小于 x 的位置其不能填 x，而上界大于 x 的位置一定不会被一个限制为 x 的区间覆盖，所以说上述事情成立。

于是可以考虑把上界不同的位置和 x 不同的限制分开考虑。对于一个枚举的上界 v，考虑进行和前面简化版问题类似的 dp。对于上界为 x 的一个位置 i 分两种情况：

  1. 没有以该位置为右端点的限制。

    那么此时可以任意填，所以把每一个位置都乘上 x，然后对于 f_{i,i} 求 \sum_{j=0}^{i-1}f_{i-1,j} 更改即可。

  2. 有以该位置为右端点的限制。

    设这些限制中左端点最大的位置为 pos，那么 0\sim pos-1 要被清 0，而 pos\sim i-1 全部乘上 x，f_{i,i} 依旧直接求前缀和即可。

上述操作可以写区间乘法区间求和线段树维护，总时间复杂度 \operatorname{O}(n\log n)。代码很长但并不难写，想清楚之后还是没什么问题的。

code