自动搬运

查看原文

来自洛谷，原作者为

	Larunatrecy 举杯邀明月，对影成三人。

搬运于2025-08-24 22:55:29，当前版本为作者最后更新于2024-10-31 11:36:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{subtask 1}$

设 $dp_{i,j}$ 表示把前 $i$ 个位置划分成 $j$ 段的最小代价，转移：

$$dp_{i,j}=\max\limits_{k=1}^idp_{k-1,j-1}+f(k,i)$$

其中 $f(k,i)$ 为区间 $[k,i]$ 内的颜色数，可以预处理出来。

询问是 $O(1)$ 的，总复杂度 $O(n^3+m)$。

$\text{subtask 2}$

有至少两个做法。

sol 1

优化第一部分的 DP，以 $j$ 为阶段，那么我们只需要维护 $dp_{k-1,j-1}+f(k,i)$ 的最大值。

开一棵线段树，第 $k$ 个位置维护 $g_k=dp_{k-1,j-1}+f(k,i)$，当我们 $i\to i+1$ 时：

• $g_{k+1}=dp_{j-1,k}$
• $\forall k>lst_{i+1},g_k=g_k+1$

其中 $lst_i$ 为 $i$ 左边第一个等于 $a_i$ 的数的下标，没有则为 $0$。

上面的转移只需要线段树支持区间加即可。

询问还是 $O(1)$ 的，总复杂度 $O(n^2\log n+m)$。

sol 2

我们不难证明 $f(k,i)$ 满足四边形不等式，因此 DP 可以用决策单调性优化。

直接分治，两个指针移动来维护 $f(k,i)$，总复杂度 $O(n^2\log n+m)$。

$\text{subtask 3}$

因为 $m=1$，所以我们只需要解决一个询问。

由于蒙日矩阵 $\max+$ 卷积的 $k$ 次幂的每个位置都关于 $k$ 凸，因此 $dp_{i,j}$ 关于 $j$ 是一个凸函数，这种区间划分问题的经典做法是 $wqs$ 二分。

二分斜率 $c$，转移为：

$$dp_{i}=\max_k dp_{k-1}+f(k,i)-c$$

然后同上用线段树优化转移，复杂度 $O(n\log^2n+m)$。

$\text{subtask 4}$

我们考虑一下 $wqs$ 二分的斜率 $c$。

那么因为 $a_i\leq 30$，所以 $f(k,i)\leq 30$，那么当 $c>30$ 时，$f(k,i)-c<0$，此时切点一定是分一段，因此只有 $c\leq 30$ 的 $c$ 有意义。

对于 $c=0\cdots 30$ 各做一遍线段树优化 DP，存下每个前缀的答案即可。

复杂度 $O(\max a_in\log n+m)$。

$\text{subtask 5}$

上一个做法告诉我们，当 $c$ 过大时，切点就会很小。

我们可以具体分析一下，设 $F(k)=dp_{*,k},D(k)=F(k)-F(k-1)$，因为 $F$ 是凸函数，所以 $D(k)\geq D(k+1)$ 恒成立。

同时，因为 $F(k)\leq n$，那么有 $(k-1)D(k)\leq \sum_{i=2}^k D(i)\leq F(k)-F(1)\leq n$，即 $D(k)\leq \lfloor\frac{n}{k-1}\rfloor$。

设斜率为 $c$ 时的切点为 $G(c)$ ，那么 $F(G(c)-1)-c\times (G(c)-1)\leq F(G(c))-c \times G(c)$ ，即 $F(G(c))-F(G(c)-1)\geq c$ ，$c\leq D(G(c))\leq \lfloor \frac{n}{G(c)-1}\rfloor$。

我们取阈值 $B$，

• 对于 $k\leq B$ 的询问，我们可以预处理所有普通 DP 值。

• 对于 $k>B$ 的询问，根据上面的性质，$G(c)\geq k$ 的 $c$ 满足 $c\leq \lfloor\frac{n}{B} \rfloor$ ，我们预处理这些 $c$ 对应的 DP 值。

都采用线段树优化，单次 DP 都是 $O(n\log n)$，取 $B=\sqrt n$，我们预处理的复杂度是 $O(n\sqrt n\log n)$。

询问时，前部分可以 $O(1)$ 回答，后半部分可以直接二分，不过这样空间是 $O(n\sqrt n)$ 的。

同时注意到 $G(c)$ 是单调的，因此可以把询问按照 $k$ 排序后，用一个指针维护转移点，空间就是线性了。

排序可以用桶排序，该做法时间复杂度 $O(n\sqrt n\log n+m)$，空间复杂度 $O(n+m)$。

注意到线段树的常数比较大，如果被卡常可以把第一部分的 $dp$ 换成决策单调性分治，因为访问时连续的所以常数小很多。如果实现较好，也可以直接获得满分。

$\text{subtask 6}$

考虑能不能把线段树的 $\log$ 去掉。

观察一下我们实际需要支持的操作：

• 向末尾加入一个数
• 后缀加 $1$
• 求最大值

维护一个单调递减的单调栈，那么 $1$ 操作可以直接不断弹栈维护，$3$ 操作就是查询栈底元素。

对于 $2$ 操作，我们找到该后缀在单调栈上对应的位置，这个可以用并查集维护，然后相当于把这个部分往前面合并弹出若干元素，最后打上 $+1$ 标记。

因为要支持中间弹出元素，所以我们用链表维护这个单调栈，至于 $+1$ 标记，我们可以发现我们相当于只需要查询栈底，查询栈顶，查询某相邻两个位置的差值，因此直接维护单调栈内元素的差分值即可，打标记是简单的。

瓶颈在于并查集，因此单次 $dp$ 的复杂度优化到了 $O(n\alpha (n))$，如果采用严格线性并查集，我们可以做到 $O(n)$。

剩下部分不变，复杂度 $O(n\sqrt n+m)$，空间 $O(n+m)$，可以通过此题。

值得一提的是，在本题中你可以发现，我们优化单次 DP 和优化多次询问的部分是独立的，也就是说，我们把 $f(l,r)$ 换成任意凸函数，在值域不大的情况下都可以在根号的代价内求出所有函数值。

代码不放了，需要的可以私聊。