题解：P10181 龙逐千灯幻
Larunatrecy
·
·
题解
\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，
都采用线段树优化，单次 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 操作可以直接不断弹栈维护，3 操作就是查询栈底元素。
对于 2 操作，我们找到该后缀在单调栈上对应的位置，这个可以用并查集维护，然后相当于把这个部分往前面合并弹出若干元素，最后打上 +1 标记。
因为要支持中间弹出元素，所以我们用链表维护这个单调栈，至于 +1 标记，我们可以发现我们相当于只需要查询栈底，查询栈顶，查询某相邻两个位置的差值，因此直接维护单调栈内元素的差分值即可，打标记是简单的。
瓶颈在于并查集，因此单次 dp 的复杂度优化到了 O(n\alpha (n))，如果采用严格线性并查集，我们可以做到 O(n)。
剩下部分不变，复杂度 O(n\sqrt n+m)，空间 O(n+m)，可以通过此题。
值得一提的是，在本题中你可以发现，我们优化单次 DP 和优化多次询问的部分是独立的，也就是说，我们把 f(l,r) 换成任意凸函数，在值域不大的情况下都可以在根号的代价内求出所有函数值。
代码不放了，需要的可以私聊。