ARC 175 C 题解
我们考虑经典套路，假设前 \(i - 1\) 个数已经被确定。
设 \(f_k(x)\) 表示 \(a_k = x\) 时 \(\sum_{i = k + 1}^n | \ a_i - a_{i - 1} \ |\) 的最小值。
那么，\(a_i = x\) 当且仅当 \(x\) 取最小值且 \(| \ x - a_{i - 1} \ | + f_i(x)\) 为所有可能中的最小值。
我们设集合 \(I_k = \operatorname{argmin}_{x \in [l_k, r_k]} f_k(x)\)。
一个奇妙性质：\(I_k\) 一定是一个区间。
感性理解。容易发现 \(f_k\) 是一个凸函数，所以当取到最小值时，取值定为一个区间。
我们考虑 \(f_k(x)\) 怎么求。
丁真一下。我们可以考虑直接贪心。若 \(a_i = p\)，则 \(a_{i + 1}\) 取 \(\operatorname{argmin}_{x \in [l_k, r_k]} | \ x - p \ |\)。然后转移还是比较简单的。
我们设 \(m_k = \min_{x \in [L_k, R_k]}\{f_k(x)\}\)：
\[f_k(x) = \begin{cases} m_{k+1} + l_k - x & (x < l_k)\\ m_{k+1} & (x\in [l_k, r_k])\\ m_{k+1} + x - r_k & (r_k < x) \end{cases} \]以上贪心可以通过大力分讨得证。
但是这一眼正确吧。
那么我们观察 \(f_k(x)\) 的转移式，发现最小值是非常能确定的。于是得到下列结论：
- 如果 \([L_k, R_k] \cap I_{k+1} \neq \emptyset\)，则 \(I_k = [L_k, R_k] \cap I_{k+1}\)。
- 如果 \(R_k < l_{k + 1}\)，则 \(I_k = R_k\)。
- 如果 \(L_k > r_{k + 1}\)，则 \(I_k = L_k\)。
综上，我们求出了 \(I\)。\(f\) 实际上不需要求出。
回到原题。我们要找到 \(x\) 使 \(x\) 取最小值且 \(| \ x - a_{i - 1} \ | + f_i(x)\) 为所有可能中的最小值。
仍然是大力分讨：
-
\(a_{i - 1} \in I_i\) 时，\(a_i = a_{i - 1}\)。
-
\(L_i \leq a_{i - 1} < l_i\) 时，\(a_i = a_{i - 1}\)。
-
\(a_{i - 1} < L_i\) 时，\(a_i = l_i\)。
-
\(a_{i - 1} > r_i\) 时，\(a_i = r_i\)。
发现上述过程可以简化为 \(a_i\) 取 \([L_i, r_i]\) 中最靠近 \(a_{i - 1}\) 的值。
CF1946E 题解
首先发现左右两部分是比较独立的，所以可以分开计算后合并。
注意到我们可以把整个数集分成左右两部分，即 \(\binom{n - 1}{p_{m1} - 1}\)。
然后我们不妨只考虑左边。
发现左边的最大值也已经确定，且最大值右边的所有数可以随便选，即 \(\binom{p_{i + 1} - 2}{p_i - 1}\)。
由于内部需要换顺序，所以还要乘上 \((p_{i + 1} - p_i - 1)!\)。
右边同理。最后的答案即为全部的乘积。
CF1923E 题解
考虑记录每一个点 \(i\) 离他最远的一个祖先使得祖先到 \(i\) 的路径上没有 \(a_i\)。设他为 \(\text{lst}_i\)。然后如果两个 \(u, v\) 的 \(\text{lst}\) 相等，那么这条路径就是好的。每种颜色枚举即可。
KEL 题解
我们考虑一个点，它的权值 \(a_i\) 在区间 \([l_i, r_i]\) 内时，我们把 \(f_i\) 标记为 \(1\)。此时，符合条件的 \(i\) 点要满足在 \(i\) 子树内的所有 \(v\)，他的 \(f_v = 1\)。
于是我们可以维护一颗线段树，线段树的值表示 \([l, r]\) 区间内有多少 \(f_i = 0\) 的数。
如果当前修改了 \(x\) 的权值导致 \(a_i\) 是否合法的状态更改，那么可以把 \(1\) 到 \(x\) 的简单路径上所有点 \(+1\)。用一个标记永久化的线段树再套一个树链剖分即可。
标签：题目,题解,最小值,链接,简记,思考,考虑,我们 From： https://www.cnblogs.com/aemmprty/p/18097876