P14135 【MX-X22-T6】「TPOI-4F」Miserable EXperience

MiniLong · 2025-10-09 20:17:11 · 题解

把子树操作放到最后来做，且子树操作合法当且仅当 \forall i,a_i \ge a_{fa_i}。

先差分一下，令 c_i = a_i - a_{fa_i}，那么就是要让 \forall i,c_i \ge 0，答案就是 \sum c_i。一次行操作就是将第 i 行的 c 减 1，i+1 行的 c 加 1，代价变化 cnt_{i+1} - cnt_{i} + 1。所以每行只和点个数 cnt_i 和 c 的最小值 p_i 有关。

先考虑 p_i \ge 0 的情况，考虑把操作 i,i+1,\ldots j 变为操作 i,j，代价为 cnt_j - cnt_i + j - i，设 b_i = cnt_i + i，即为 b_j - b_i。这样处理后就不存在形如 (i,j),(j,k) 这样的重合操作了，所以每个点要么是只出，要么只进，对于只出的点，要求操作的次数 \le p_i（否则就小于 0 了）。贪心地，把每个点按 b_i 从小到大排序，每次取出最小的 b_i 把前面没匹配的都和它匹配即可（也即每个点向其后缀最小值匹配）。

对于存在 p_i < 0 的情况，可以先任意操作若干次将 p_i 都变成非负数再继续调整，只要调整能最优，那么肯定可以到达最优答案。

考虑优化，由于只和后缀最小值之类的后缀信息相关，长链剖分后合并短链的时候大于短链长度的部分可以直接继承，前面直接暴力做就行。

实现方法可以用指针数组实现，方便很多。

复杂度 \Theta(n)。