题解：AT_agc049_e [AGC049E] Increment Decrement

· · 题解

[AGC049E] Increment Decrement

link luogu link

学习了 O(n^4 K) 做法和 O(n^3 K) 做法。

我们对于每一个 B_i = [A_i \ge x] 考虑把 B 清空的代价，可以证明把每一层的贡献加起来即为答案。

我们考虑证明每一种操作序列都可以通过调整使得让每一个操作都属于仅一层，且每一层的操作合法。先把区间操作全部放到单点操作前面，不难发现单点操作的规约是容易的。考虑将区间操作转换为在差分数组上面操作，然后在差分数组上面将 x 视为 x 个左括号，-x 视为 x 个右括号，转换后的括号串一定是合法括号串。然后进行括号匹配，将匹配上的一对括号视为对这个区间的一次操作。容易发现括号匹配转换出来的操作次数和原操作次数相等，且一定可以把括号匹配转换出来的操作扔到一层上考虑。至此我们简要证明了为什么可以分层考虑。

然后不难发现本质不同的 B 序列只会有 O(nK) 种，那么我们可以枚举当前层 x 然后算贡献。

设 f_i 为已经使得 B_{1:i} 已经操作好的次数，分成区间操作和单点操作两种转移，具体的就是 f_i = \min \{ f_{i-1}+[b_i = 1],f_k + s_i - s_k + C \}，其中 s_i 表示前缀 0 个数。那么我们考虑直接维护 mn = \min(f_k + s_i - s_k)，每次就是让 mn \leftarrow \min(mn+[b_i = 0],f_i)。然后可以做 O(1) 转移。

考虑扔到变化上面的怎么求，设 dp_{i,j,k} 为 f_i=j,mn=k 的方案数，然后算一下有多少种方案使得 b_i = 0，可以做到 O(1) 转移。因为答案肯定不会超过 n 次单点操作，所以状态数是 O(n^3) 的。

对于 O(nK) 层每一层复杂度为 O(n^3) - O(1)，总复杂度 O(n^4K)。

重新转化一下题意，维护一个初始全为 0 的序列 C，通过若干次操作使得 C=A。

我们还是先把区间操作全部放到单点操作前面，对于只进行区间操作后的序列 C，答案为 cost + \sum |a_i - c_i|，其中 cost 为所有区间操作的代价。考虑那个差分加括号串转换，发现区间操作次数即为左括号个数，即差分 >0 的所有值总和。设 f_{i,j} 为 c_i=j 并且处理了 [1,i] 的所有数的最小代价，有转移 f_{i,j} = |a_i - j| + \min_k(f_{i-1,k} + C \times \max(j-k,0))。

发现 f_i 是下凸函数，考虑 slope trick 优化转移。每次先 f_{i-1,j} \leftarrow \min_{k}(f_{i-1,k} + C \times \max(j-k,0))，然后 f_{i,j} = f_{i-1,j} + |a_i-j|。简单分析可以发现前面的式子保证了斜率值域为 [0,C]，再加上一个绝对值函数所以 f_i 的斜率值域为 [-1,C+1]。前面的式子可以看作将斜率 -1 \rightarrow 0,C+1 \rightarrow C，那么要是维护出 C+2 个转点就可以每次拍平第一个和最后一个转点，然后再加入两个下标为 a_i 的转点表示 a_i 这个地方斜率变化量为 2，我们就可以用 multiset 之类的实现对于单个 A 序列 O(n \log n) 求出答案。

初始状态即为 f_{0,i} = C \times i，所以最开始你要往 S 塞入 C+2 个 0。

考虑算答案。如果你得出来了最终的转点集合 S，那么其中 -1 \rightarrow 0 的转点位置即为 S 最小值，我们记为 p_n。那么最终答案即为 f_{n,0} - p_n。考虑怎么算 f_{n,0}，它是上一段的 -1 \rightarrow 0 的转点拍平后再加上绝对值 |a_n - 0| 得到的结果，所以 f_{n,0} = a_n + (f_{n-1,0} - p_{n-1})，通过归纳可以得到最终答案的形式可以写为 \sum\limits_{i=1}^n (a_i - p_i)，这个在扫一遍的时候同时处理下就可以了。

考虑原问题，现在 A 序列会变化。但是最终答案的形式好像挺简洁，可以拆贡献先对所有 A 求和再减去所有 p_i 就可以了。发现维护出来一个 p_i = x 的方案数比较困难，考虑维护出 p_i \le x 的方案数。

枚举 x，设 dp_{i,j} 为维护到了 i，当前集合中有 j 个数 \le x 的方案数。计算删掉最小值和最大值后还剩几个数 \le x 和当前位置 \le x 的数的个数后，容易做到 O(1) 转移。初始状态即为 dp_{0,C+2} = 1。

容易发现集合中只会出现 A 中的数，所以 x 的枚举量是 O(nK) 的，dp 复杂度为 O(n^2) - O(1)，总复杂度为 O(n^3K)。