题目大意

就是说现在有序列 $a_1,a_2,a_3,...,a_n$ ，我们每一次操作可以选择一个位置 $i$ ，将 $i$ 这个后缀加或减一些数（如题）。然后我们要求出将序列变成 $k,k,k,k...$的最小操作数。

解题思路

我们先将给出的数组都减去 $k$ 得到一个“需求数组” $c_1,c_2,c_3,..,c_n$，我们的任务就是通过加减填满所有“需求”。但是我们暴力加的话是 $O(n^2)$ 的。

（我原本试图将 $ C_{i - j + p}^{p} $ 拆成 $i,j$ 独立的式子,但失败了。）

先说一个结论：

有两个序列 $A = a_1,a_2,a_3,...$ 和 $B = b_1,b_2,b_3,...$， $A + B$ 的差分序列 $= A$ 的差分序列 $+ B$ 的差分序列。即 $a_i + b_i - a_{i-1} - b_{i-1} = (a_i - a_{i-1}) + (b_i - b_{i-1})$

就是说我们将 ${c_1,c_2,c_3...}$ 和 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 都差分再用后者将前者全补成 $0$ 等价于原问题。有

$$C_{n}^{m} = C_{n - 1}^{m - 1} + C_{n - 1}^{m}$$

在 $C_{p}^{p},C_{p + 1}^{p},C_{p + 2}^{p}...$ 中 $C_{p}^{p} = C_{p - 1}^{p - 1} = 1$,$C_{p + i}^{p} - C_{p + i - 1}^{p} = C_{p + i - 1}^{p - 1}$。也就是说对序列的一次差分就是将上下标都减1。

于是我们只要进行 $p$ 次差分就能将原序列变为 $1,1,1,1...$。$p - 1$ 次差分即为 $1,0,0,0,...$

所以我们将 $c$ 数组也进行 $p - 1$ 次差分,随后答案就是 $ans = \sum_{i = 1}^{n} | c_i |$

【PA 2020】Miny

P9100 [PA 2020] Miny - 洛谷

给出每一个炸弹 $i$ 的位置 $a_i$ 和爆炸半径 $r_i$，每次爆炸都会使得 $[a_i - r_i, a_i + r_i]$ 范围内的炸弹爆炸，发生连锁反应。起爆的炸弹集合不定，问你最终的局面的方案数。

$1 \le n \le 3 \times 10 ^ 5, 0 \le a_i, r_i \le 10 ^ {18}$。

我们考虑 dp 的转移。

发现其实我们并不能得到一个很好的没有后效性的东西。

我们不妨发挥人类智慧，设计一个好的的 dp 状态。

我们设 $dp_i$ 表示，前 $i$ 个炸弹，以 $i$ 结尾，且钦定 $i$ 不爆炸的方案数。那么我们枚举 $j < i$ 进行转移，当且仅当 $[j + 1, i -1]$ 这部分的炸弹爆炸不会波及到 $i$ 和 $j$ 这样才能满足我们设定的不爆炸的钦定。 为了更好的判断是否波及，我们设 $L_i$ 表示左边能引爆 $i$ 的最大的炸弹，$R_i$ 表示右边能引爆 $i$ 的最小的炸弹。换言之就是最近且能引爆 $i$ 的。 这个过程我们可以用单调栈维护，我们可以通过单调栈，扫描两次，第一次求 $L$，第二次求 $R$，那么由于随着下标的增长，$a_i$ 是不断增加的，我们要想知道 $i$ 左边的第一个能引爆 $i$ 的，我们需要在单调栈中维护能覆盖 $a_i$ 的，最大的下标。若是当前的栈顶无法满足，就弹出，找前面的是否有能满足的。 对于这样的操作，我们再从后往前扫一次即可得到 $R$。

那么我们的 dp 可以转化为：

$$ dp_i = \min_{j < i \text{ and } (L_i \le j) \text{ and } (R_j \ge i)}(dp_i = dp_j + dp_i) $$

对于这个操作实际上是 $n ^ 2$ 的，我们考虑优化。

我们不难发现，满足条件 $L_i \le j$ 的序列，实际上下标直接就可以从 $L_i$ 开始一直到 $i$。

换言之，我们答案就是 $j \in [L_i, i - 1] \text{ and } R_j \ge i$ 的 $\sum dp_j$。

对于这样的询问，我们难免会想到在处理完当前的 $i$ 之后，把 $dp_i$ 插入到树状数组中，然后问 $[L_i, i - 1]$ 的时候，直接用树状数组做前缀和差分即可。

但是问题就在于，我们在询问 $L$ 的时候，插入的 $dp_i$ 实际上是只有 $[0, L]$ 的部分的 $R_j \ge i$ 的部分，可是留到最后算是会出问题的。

这个时候就可以用两种方式解决这个问题。

第一种方式是主席树，我们考虑把不同版本存下来，问 dp 的时候，只需要找到 $L_i - 1$ 的版本和 $i - 1$ 的版本即可。

第二种方式，我们把需要用到的询问离线下来，每次做完当前 $i$ 的操作之后，把挂在 $i$ 上的询问的答案都计算出来。

时间复杂度 $\mathcal{O}(n \log n)$。

【JOI 2017 Final】足球 / Soccer

P5100 [JOI 2017 Final] 足球 / Soccer - 洛谷

在二维网格球场上有 $N$ 名球员，求通过球员移动/运球（每步疲劳度为 $C$）以及踢球（踢出距离 $p$ 疲劳度为 $A \times p + B$）相互配合，将足球从 $1$ 号球员处转移到 $N$ 号球员初始位置所需的最小总疲劳度。

$1 \le W, H \le 505, 1 \le A, B, C \le 10 ^ 9, 1\le n \le 10 ^ 5$。

我们考虑到球的状态，球要么是被人带着，要么是在被踢的状态。

考虑拆点做分层图或者拆状态。

我采用的方式是拆状态。

我们设 $d_{x, y, st}$ 表示在 $(x, y)$ 这个位置，状态是 $st$ 的最小花费。

这里我们设 $5$ 种状态，由于被踢的状态是特殊的，我们单独处理。因为被踢的时候只能沿着本方向一直走。我们定义 $\{ 0, 1, 2, 3, 4\}$ 分别表示被踢的时候，上下左右，和被带的时候，分别在最短路的时候转移。

但是被踢转换到被带的时候，需要找到最近的球员进行接球，这个过程需要预处理每一个格子最近的球员，可以用多源的 BFS 完成这个预处理。

时间复杂度 $\mathcal{O}(HW \log (HW))$。

【ARC215A】Zombie

AT_arc215_a [ARC215A] Zombie - 洛谷

给出 $n$ 个僵尸的位置，在一个长为 $L$ 的数轴上，你需要放 $k$ 块脑子，每个僵尸每秒都会向脑子方向移动 $1$，问脑子存在的最长时间和。

$1 \le n \le 2 \times 10 ^ 5, 1 \le k \le 10 ^ 9, 1 \le a_i \le 10 ^ 9, 1\le L \le 10 ^ 9$。

其中，所有僵尸的位置均为偶数。

我们考虑贪心的策略，其中，对于贪心策略来讲，无非就是选择中间或者两边。

我们将中间的区间按大小排序，枚举选多少个区间，直接预处理前缀和，或者枚举的时候累计，最后 $\mathcal{O}(1)$ 计算剩余的脑子放在两边的方案数。

时间复杂度 $\mathcal{O}(n \log n)$。

【MX‑S15‑T2】「DLESS‑5」宇宙射线

P16996 【MX‑S15‑T2】「DLESS‑5」宇宙射线 - 洛谷

给出一个 $n$，并给出 $1 \sim n$ 的排列 $a$，问在冒泡排序的某一次的执行是相反的，问最终能产生的本质不同的 $a$ 的数量。

$1 \le n \le 2 \times 10 ^ 6, 1 \le a_i \le n$。

学校模拟赛 T2，全世界都把这个题切了，除了我。我的这篇题解的思路来自学弟 @Zjh6666，膜拜。

在阅读本篇题解之前，最好先独立思考关于这个题目的做法。

本文所讨论的序列默认为排列。

冒泡排序的本质

冒泡排序的本质是在每一轮的操作中，从一个未排序的前缀中找出最大的值，将其推到当前这段前缀的末尾。

形式化的讲，对于第 $r$ 轮，后面的 $i \in [n - r + 2, n]$ 时，$a_i = i$。而对于前面的 $[1, n - r + 1]$ 是未正确排序的。而我们本轮的操作就是找到 $\max_{i \in [1, n - r + 1]} a_i$，并将其推到 $n - r + 1$ 的位置。

考虑最终态

知道了冒泡排序的本质之后，我们实际上就可以分析出来这个题的最终态。

对于 $1 \sim r - 1$ 轮，排序是无错的，但考虑到如果在第 $r$ 轮时，操作被宇宙射线照射，那么就存在一个 $x$，被推到 $n - r + 1$，并永久固定。对于 $r + 1 \sim n - 1$ 轮继续执行无错的冒泡排序。

结论

由最终态我们可以得到，最终的排列 $a$ 完全由二元组 $(k, x)$，即 $x$ 在第 $k$ 轮被固定在了位置 $n - k + 1$，最终得到的序列的形式如下：

$$a_{(k, x)} = \{ 1, 2, \dots, x - 1, x + 1, \dots, n - k + 1, x, n - k + 2, \dots , n \}$$

这个序列被清晰的分为三段：

• $[1, n - k]$ 位：最后 $n - k + 1$ 轮，由刨除 $x$ 之外的剩下的 $n - k$ 个数形成的完全升序的序列。
• $n - k + 1$ 位：第 $k$ 轮的宇宙射线使得 $x$ 被推到 $n - k + 1$ 的位置。
• $[n - k + 2, n]$ 位：前 $k$ 轮的排序，使得这段完全升序。

如何统计二元组？

考虑分类讨论关于二元组 $(k, x)$ 的贡献。

升序态

考虑唯一一次的宇宙射线没有对序列的冒泡排序产生影响。这样我们的序列最终就能达到完全升序的情况。这里我们只需要构造出任意一种合法的方案即可以升序。

考虑自愈的情况，即就算射线造成影响，也依然能做到在后面的冒泡中自愈。这种情况，当且仅当第 $n - x + 1$ 轮的最大的数 $x$ 没有被射线影响，依然正常归位。

而归位的条件就是当前需要归位的 $x$ 在序列中的位置 $\ge 3$，定义 $x$ 初始的位置在 $pos_x$，则可以表述为 $pos_x \ge n - x + 3$。

因此如果对于任意一个 $x$ 满足上述的等式，则完全升序成立。记 $1$ 的贡献。

相邻态

即最终的形态只是相邻的两个位置发生了错误的互换，这种情况当且仅当在某一轮的最后一次互换时发生宇宙射线。

具体来说，对于第 $k$ 轮，最大值应为 $n - k + 1$，但是此时变成了 $n - k$，则最终的序列为：

$$a_{(k, n - k)} = \{ 1, 2, \dots, n - k - 1, n - k + 1, n - k, n - k + 2, \dots \}$$

即 $n - k + 1$ 和 $n - k$ 受宇宙射线影响交换。这种操作可以在每一轮进行，则固定有 $n - 1$ 次贡献。

跨越态

对于当前的第 $k$ 轮，既不是 $n - k + 1$，也不是 $n - k$ 被移动到最右端，而是 $x < n - k$ 的数被移动到了本轮的最右端。

此时的序列形态和我们所说的传统态是一样的：

$$a_{(k, x)} = \{ 1, 2, \dots, x - 1, x + 1, \dots, n - k + 1, x, n - k + 2, \dots , n \}$$

$x$ 数跨越了 $[x + 1, n - k + 1]$ 位置的所有值，一路向右被固定在 $n - k + 1$ 的位置。

我们换视角，考虑对于一个元素 $x$ 做贡献的情况，若 $x$ 能产生跨越的贡献，则一定是后缀最大值，则能在 $[x + 2, n]$ 的位置产生贡献，此时记 $n - (x + 2) + 1 = n - x - 1$。

为什么一定是后缀最大值？
如果 $x$ 右边存在一个 $y > x$，那么在错误发生之前的正常冒泡过程中，$y$ 会被推到 $x$ 的右边并优先参与后续归位，因此 $x$ 不可能在错误发生的那一轮成为被错误推到末端的元素。

因此对于答案的统计，我们维护后缀最大值，每次如果有当前值大于后缀最大值，说明后面的位置都可以用，贡献即 $\sum_{a_i \text{是严格后缀最大值}} \max(0, n - a_i - 1)$。

场上想出了正解太复杂了以为假了没写，结果赛后发现和正解一模一样，空悲切。

首先这一看就能 dp，考虑设 $f_i$ 表示以 $i$ 为根的子树分为若干链的最小代价，每次枚举一条以 $i$ 为端点的链，枚举另外一端 $j$。

考虑贡献，首先有这条链的贡献，其次有 $j$ 的所有儿子的子树划分为链的贡献，然后又 $i\to j$ 路径上，因为把 $i\to j$ 割掉后分出的各个子树的贡献。

设 $h_u=\sum_{v\in son(u)}f_v,g_u=\sum_{v\in bro(u)}f_v$，另外设 $s_u$ 表示根到 $u$ 的所有边权之和，$sg_u$ 表示根到 $u$ 的 $g_i$ 之和，不难写出一个转移：

$$f_u=\min_{v\in Subtree(u)}\{h_v+(s_v-s_u)^2+C+(sg_v - sg_u)\}$$

如果暴力转移，$h,g,sg$ 都可以 $O(n)$ 处理，主要是 $f$ 的转移是 $O(n^2)$ 的。

注意到这是一个经典的斜率优化形式，考虑斜率优化，因为在树上进行，考虑李超树，唯一的问题是直线的截距 $sg_u$ 可能会需要子树加。

实际上，在合并李超树的时候，顺路维护一个全局加的标记即可，这个标记可以在合并的时候打在根上。

时间复杂度为 $O(n\log n)$。