ARC072
A
不难用调整法证明贪心的正确性，于是直接贪即可。
B
打了个表发现 Alice 能赢当且仅当 \(|x - y| > 1\)。证明大概就是对于 \(|x - y| \le 1\)，一次操作之后必然有 \(|x' - y'| > 1\)；对于 \(|x - y| > 1\)，又可以进行操作使得 \(|x' - y'| \le 1\)，最后必然会到 \(x, y = 0, 1\) 的状态。
C
首先求出前 \(i\) 次操作之后的距离，记为 \(dis_i\)。那么修改操作实际上就是令 \(dis_i \leftarrow dis'_i\)，满足 \(dis'_i \in [0, dis_i]\)，然后继续推。所以我们要解决的是对于 \(dis'_i = 0, 1, \cdots, dis_i\)，最后推出来的结果是否都为 \(0\)。
接下来是最神仙的一步：我们考虑维护 \(f_i\) 表示最大的 \(v\)，使得初始距离为 \(0, 1, \cdots, v\) 时进行第 \(i, i + 1, \cdots, n\) 个操作，最后的距离都是 \(0\)。发现这个是可以推的。具体地，设第 \(i\) 次操作时的初始距离为 \(v_0\)，那么我们只需要
\[\min\{v_0, |v_0 - a_i|\} \le f_{i + 1} \]为什么？不难发现这个函数是连续的，所以 \(v_0\) 逐渐增长的过程中绝对不会出现 \(v\) 跳出 \(f_{i + 1}\) 这个前缀来到另一个非前缀但是最后距离为 \(0\) 的解的情况，所以转移的时候只用考虑前缀即可。最终判断的时候看一下这个前缀是否大于前面的 \(dis\) 即可。
时间复杂度 \(\mathcal{O}(n)\)。
D
考虑动态修改方案。假设我们当前必须要在某个时刻多排出一些水，那一定是在总水温最小的时刻。发现如果即将加的水温大于当前的水温，那么肯定排完再加比加完再排更优；反之亦然。所以我们可以把所有的温度递减的子区间提出来，放到一个单调队列里，每次取温度最低的，相当于在那个时候再多排一些。
时间复杂度 \(\mathcal{O}(n)\)。