题解：P12481 [集训队互测 2024] 运筹帷幄

感谢 _LHF_同学将本题的空间复杂度优化到了 $O(n)$，加强版链接：https://www.luogu.com.cn/problem/P11690。

基本的贪心

贪心证明

• 选择棋子移动到 $x$ 是不劣的，因为假设选择了第 $p$ 个棋子移动到 $x$，那么距离序列就变成了 $a'=\{0,a_1,a_2,\cdots,a_{p-1},a_{p+1},a_{p+2},\cdots,a_k\}$。
  注意到，$a'$ 序列能全维偏序 $a$ 序列（这里全维偏序是指所有对应位置的数都有 $a'_i\le a_i$，下同）。
  所以，我们可以说明选择棋子移动到 $x$ 是不劣。
• 选择第 $k$ 个棋子移动到 $x$ 是不劣的，因为假设选择了第 $p\ne k$ 个棋子移动到 $x$，那么距离序列就变成了 $b=\{0,a_1,a_2,\cdots,a_{p-1},a_{p+1},a_{p+2},\cdots,a_k\}$。
  假设选择了 $a_k$ 移动到 $x$，那么距离序列就变成了 $b'=\{0,a_1,a_2,\cdots, a_{k-1}\}$。
  注意到，$b'$ 序列能全维偏序 $b$ 序列。
  所以，我们可以说明选择距离最远的棋子移动到 $x$ 是不劣。

维护

1. 继承 $f_{\mathrm{hson}_x}$ 的状态；
2. 加入轻儿子 $y$ 贡献。由于我们维护的是后缀和，而每次修改是一段前缀，因此我们可以维护；
3. 将前 $a_x-b_x$ 大删除，我们在 $f$ 数组上二分，即可更新 $\mathrm{sum}_x$。

• 用数组来维护 $F_i$ 表示到 $x$ 距离 $\ge i$ 的棋子数量。
  $G_i$ 表示到 $x$ 的距离 $\ge i$ 的棋子到 $x$ 的距离和。

1. 根据 $f_x,g_x$ 回退出 $f_{\mathrm{hson}_x},g_{\mathrm{hson}_x}$；
2. 我们先将所有轻儿子都加入 $F$ 里面；
3. 对于重儿子：不需要做额外处理；
4. 对于轻儿子：我们先将结点 $y$ 在 $f$ 内的贡献删除，然后再截取重儿子距离 $\le \mathrm{size}_y$ 的部分，对于重儿子 $f_{\mathrm{wson}_x}$ 中 $>\mathrm{size}_y$ 的部分，我们将重儿子的结点编号 $\mathrm{wson}_x$ 加入 $S_y$ 内，并记录 $\mathrm{size}_y$；
5. 将 $f_{\mathrm{hson}_x},g_{\mathrm{hson}_x}$ 还原成 $f_x,g_x$。