11.13 写题

AGC006

已单独开坑。

CF1083A

显然，点权减边权最大的路径上不可能存在让油量变成 $0$ 的一段。所以找点权减边权最大的路径，这个可以直接 $dp$。

CF1083B

首先，我们把 $s,t$ 都直接拿一遍肯定是前两步的最优操作。相当于除了 $s,t$ 的 $lcp$ 其他部分都拿了两遍。

然后可以直接把 $lcp$ 给丢掉了。现在，对于 $s$ 的每一个 $0$ 位置，我们如果在这里放 $1$ ，我们可以有 $1$ 个贡献为 $n-i+1$ 的串，一个贡献为 $n-i$ 的串，两个贡献为 $n-i-1$ 的串，四个 $n-i-2$ 的串 $\dots$

把这个贡献放到一个差分数组上，这个数字表示一个给下个位置这个位置两倍的差分即可。

然后贪心拿前 $k$ 大。

具体参考代码把。。反正就这么整了下就过掉了。。

CF1083C

离谱。打 vp 的时候想了想不太会看到场上都在写 E 就去整 E 没管了。。然后 C 2800 , D 3500 , E 2400 , F 3300...，而且这四个东西还标签还都是 data structure 。。

这个题思路还算简单，考虑在值域上开一个线段树，维护如果想要同时包含区间内的值的最小路径，或维护不存在这样的路径。这个东西的合并就是一个路径求并的过程，而且如果合并后不是路径直接判掉即可。查询就是线段树上二分，修改就直接单点改。

如果像我一样信仰一波直接倍增 LCA 然后就 T 飞了。。。倍增求 LCA 的话这东西复杂度 $O(n\log^2 n)$ ，试了试由于 pushup 常数不小跑不过去。

然后改成 ST 表就过了。复习一下，ST 表求 LCA 的方法是记一个进入一个点记录一次的欧拉序，回溯到这个点也算数，然后找 $u,v$ 在序列中第一次出现的位置之间的最浅点即可。

复杂度 $O(n\log n)$。

CF1083E

按照 $x$ 排序， $y$ 单调递减。然后一个很一眼的 $dp$ ：

$dp[i] = \max\{dp[j] - x_jy_i + x_iy_j - a_i\}$

显然斜优， $y$ 单减求最大，用单调队列维护一个上凸壳即可。

CF1083F

考虑 $c_i = a_i\oplus b_i$ ，然后现在就是在 $c_i$ 上进行区间异或，求把 $c_i$ 变成 $0$ 的最小代价。这种东西看着就得转差分，设 $d_1 = c_1 , d_i = c_i \oplus c_{i-1} (i \ge 2)$ ，然后 $d$ 数组的前缀和就是之前的 $c_i$ 。于是区间异或就变成了 $d_i \oplus x , d_{i+k} \oplus x$ 。可以想到我们按照模 $k$ 分类，然后就变成了相邻同时异或。

然后考虑，每次操作是作用于相邻两个，同时异或的值就是前缀的异或和。如果一个位置在上一个位置操作后变成了 $0$ 就没有必要再进行操作了，所以可以节省步骤必然是一段前缀异或为 $0$ 的位置。同时，如果全部异或起来不是 $0$ 那么一定没法构造出方案。

然后现在修改就是在差分数组上进行单点修改，也就是进行某个组内的后缀修改。

后缀修改，查询 $0$ 的位置，我们考虑分块，然后块内整体修改打标记非整体重构即可。

注意块的大小。空间复杂度是 $O(k \frac{n}{kB} \times 2^{14})$ ，得把 $B$ 调整到 $\sqrt n$ 级别。

其次，得判一下 $k > \sqrt n$ 的情况，这种情况我们直接暴力，如果分块每个组都开个块可以卡成 $n \times 2^{14}$。