[CF2159D1 / 2] Inverse Minimum Partition 题解

上大分场，Div. 2 Rank 8，紫名祭。

不妨设值域为。首先你需要发现一堆有关与的性质。

性质一

下文中，「是后缀最小值」当且仅当。

我们发现，对于，如果存在满足，那么让作为子段的结尾一定不优。即，当且仅当是后缀最小值时，位置才可能作为子段的结尾。同理，当且仅当是后缀最小值时，位置才可能作为子段的开头，否则一定不优。

于是，我们只需要关注原序列中是后缀最小值的元素。

性质二

考虑对于一个非空数组，什么时候最优的划分方案是一定其本身（即不进行划分）。

设是一个非空数组，我们将其分为两个非空子段。根据性质一，我们可以认为均单调递增。容易发现，。要使的最优的划分方案一定是其本身，那么一定有。解一下这两个方程，就可以得到。

即，在最优划分中，每个子段的代价一定是中的一个。

D1 做法

我们只用关注是后缀最小值的元素。

设表示，考虑转移。因为每个子段的代价一定是中的一个，所以我们可以通过双指针维护，表示是中第一个满足的元素。那么有转移。于是 D1 就做完了。

时间复杂度。

性质三

根据性质一，我们可以认为单调递增。考虑对贪心构造出一种较优的方案。一个自然的想法是要求每一个子段的花费且总子段数量尽量少。这样，对于子段，一定有。这意味着最多只有个子段，那么的上限就是 。

性质四

考虑 D2 的暴力 DP。容易想到设表示。若我们固定，那么我们可以通过单调栈维护中是后缀最小值的元素，而可以通过二分求出。时间复杂度。

一个显然的性质是，对于固定的，单调递减。

D2 做法

性质三说明，的值域较小；性质四说明，数组在固定时具有单调性。于是我们可以利用一个经典 trick：交换 DP 的下标与值。

设表示最小的使得。那么转移是显然的：。特别地，令。初始状态是。

考虑如何统计答案。容易发现，，根据这一点统计即可。需要注意的是，因为 DP 是在单调栈上进行的，所以使用的下标均为单调栈的下标，要计算实际的下标还需要稍作转换，详见代码实现。

时间复杂度。