题解：P10181 龙逐千灯幻

喵仔牛奶 · 2026-01-23 15:18:27 · 题解

区间颜色数显然满足四边形不等式，因此答案关于 k 上凸。

答案值域是 [1,n]，那么相邻两个点斜率的和是 n，此时若 k\ge\sqrt n 则斜率 \le\sqrt n。对 k\le\sqrt n 和斜率 \le\sqrt n 分别 DP 即可。

DP 的过程是：后缀 +1，在最后加数，求全局 \max。容易发现只有后缀最大值有用，使用并查集维护每个数后面第一个后缀最大值，对于后缀最大值维护和前面的差分。复杂度 \mathcal O(n\sqrt n\alpha(n))。