20250930

Luogu 13345

先根据排序方案确定最终顺序。下文称第 \(i\) 个人为最终排名为 \(i\) 的那个人，其原始编号为 \(id_i\)，总成绩为 \(v_i\)。

若第 \(i\) 个人公布了 \(c_i\) 道题，公布部分成绩为 \(s_i\)，则可能成绩区间为 \([s_i, s_i + k(m - c_i)]\)，有 \(s_i + k(m-c_i) + [id_i < id_{i-1}] \le s_{i-1}\)。

考虑 DP，设 \(f(i, s)\) 表示前 \(i\) 个人，第 \(i\) 个人公布部分成绩 \(\ge s\)，的最小公布部分总数。先考虑等于 \(s\)，枚举 \((c, s)\)：

\[f(i, s) = \min_{(c, s)} f(i - 1, s + k(m - c) + [id_i < id_{i-1}]) + c \]

然后取一轮后缀 \(\min\) 即可得到真实的 \(f(i, s)\)。

可以通过暴力 DP 找出第 \(i\) 个人合法的 \((c, s)\)。\(O(m)\) 阶段，\(O(m)\) 枚举 \(c\)，\(O(mk)\) 枚举 \(s\)，这部分复杂度 \(O(nm^3k)\)。

事实上，因为 \(s \le v_i\)，只有 \(s \in [v_{i+1}, v_i]\) 的可能是合法的，令 \(l_i = v_i - v_{i+1} + 1\)，至多只有 \(ml_i\) 种 \((c, s)\)，且 \(\sum l_i = n + mk\)。

为保证复杂度，通过从全部公布倒着 DP 未公布的部分找 \((c, s)\)，单轮 \(O(m^2l_i)\)，把 \(c\) 用 __int128 压一下可以消掉一个 \(m\)。

总时间复杂度：\(O(nm + m^2k)\)。

Luogu 9521

从 \((x_1, y_1)\) 到 \((x_2, y_2)\)。

• 经过 \((x_1, y_2)\)：\(a_{x_1}(y_2-y_1) + b_{y_2}(x_2-x_1)\)；
• 经过 \((x_2, y_1)\)：\(a_{x_2}(y_2-y_1) + b_{y_1}(x_2-x_1)\)。

\[a_{x_1}(y_2-y_1) + b_{y_2}(x_2-x_1) < a_{x_2}(y_2-y_1) + b_{y_1}(x_2-x_1)\iff \frac{b_{y_2} - b_{y_1}}{y_2 - y_1} < \frac{a_{x_2} - a_{x_1}}{x_2 - x_1} \]

因此会优先走斜率小的那边。

• 经过 \((x_3, y_1)\) 和 \((x_3, y_2)\)：\(a_{x_3}(y_2 - y_1) + b_{y_1}(x_3 - x_1) + b_{y_2}(x_2 - x_3)\)。

若比上面两个方案都要小：

\[\begin{aligned} &a_{x_3}(y_2 - y_1) + b_{y_1}(x_3 - x_1) + b_{y_2}(x_2 - x_3) < a_{x_1}(y_2-y_1) + b_{y_2}(x_2-x_1)\\ &\iff\frac{a_{x_3} - a_{x_1}}{x_3-x_1} < \frac{b_{y_2} - b_{y_1}}{y_2-y_1}\\ &a_{x_3}(y_2 - y_1) + b_{y_1}(x_3 - x_1) + b_{y_2}(x_2 - x_3) < a_{x_2}(y_2-y_1) + b_{y_1}(x_2-x_1)\\ &\iff\frac{a_{x_2} - a_{x_3}}{x_2-x_3} > \frac{b_{y_2}-b_{y_1}}{y_2-y_1}\\ &\therefore \frac{a_{x_3} - a_{x_1}}{x_3-x_1} < \frac{b_{y_2} - b_{y_1}}{y_2-y_1} < \frac{a_{x_2} - a_{x_3}}{x_2-x_3} \end{aligned} \]

只有下凸壳上的点，可能岔出去并在另一条坐标轴的方向上移动，会是有用的。

维护两个下凸壳，双指针即可，\(O(n)\)。

Luogu 9732

对一个区间，它的答案 \(f(l, r)\) 为：\(s_i\) 前 \(k\) 大的和减去 \(c_i\) 的总和。令 \(g(l, r)\) 表示区间前 \(k\) 大的和。

经过一些分类讨论，得出：区间前 \(k\) 大满足四边形不等式 \(g(l, r) + g(l+1, r+1) \ge g(l, r + 1) + g(l + 1, r)\)。

因为不等式两边减去同样的数，所以 \(f\) 满足四边形不等式，原问题有决策单调性。

用主席树做区间前 \(k\) 大，设 \(p_i\) 为右端点为 \(i\) 的最优左端点，答案相同取最靠右的，进行决策单调性分治可以 \(O(n \log^2 n)\) 完成第一问。

第二问，对于 \(f(l, r) = ans\) 的 \([l, r]\)，若区间第 \(k\) 大为 \(v\)，则区间内所有 \(\ge v\) 的数都能出现在一种方案中。

称一个右端点 \(r\) 是合法的，当且仅当 \(f(l, r) = ans\)。对于当前合法右端点 \(r\)，上一个合法的右端点为 \(r'\)，那么只需要考虑 \(l \in [p_{r'}, p_r]\)。

证明不需要考虑 \(l < p_{r'}, f(l, r) = ans\) 的情况：

引理：\(f(l, r) - f(l, r') \le f(p_{r'}, r) - f(p_{r'}, r')\)。

引理的证明考虑等价于 \(g(l, r) - g(l, r') \le g(p_{r'}, r) - g(p_{r'}, r')\)。这是成立的，因为向一个集合加入一些元素，其前 \(k\) 大之和的增量，不小于向其超集加入的增量。

根据引理以及 \(f(l, r) \le f(p_{r'}, r')\)，\(f(p_{r'}, r) \le f(p_r, r)\)，可知：\(f(l, r) = f(p_{r'}, r) = f(p_r, r) = ans\)，\(f(l, r') = f(p_{r'}, r') = ans\)。

也就是说，\(f(p_{r'}, r)\) 和 \(f(l, r')\) 都会先被考虑。而区间 \([l, r]\) 的第 \(k\) 大一定不小于 \([p_{r'}, r]\) 或 \([l, r']\) 的第 \(k\) 大，不会让更小的数出现在方案中，于是这样的区间 \([l, r]\) 可以被忽略。

扫描线，拿树状数组维护即可。