题解：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

分两种情况：

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

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

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

上述操作可以写区间乘法区间求和线段树维护，总时间复杂度

\operatorname{O}(n\log n)

。代码很长但并不难写，想清楚之后还是没什么问题的。