自动搬运

查看原文

来自洛谷，原作者为

	qiuzx GGMU

搬运于2025-08-24 22:45:21，当前版本为作者最后更新于2024-10-03 18:54:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这个问题中每个点对于两个人的价值是不一样的，所以不好直接看出策略，因此我们需要尝试让每个点对两个人有相同的价值。设一个点到 $A$ 和 $B$ 的距离分别为 $a$ 和 $b$，则如果 A 获得了这个点，会对最终答案产生 $a$ 的贡献，否则如果 B 获得了这个点，会对最终答案产生 $-b$ 的贡献。由于最终没有未被选择的点，所以可以先让这个点对答案产生 $\frac{a-b}2$ 的贡献。这样如果 A 选了它，答案会增加 $\frac{a+b}2$，如果 B 选了它，答案会减少 $\frac{a+b}2$，于是我们将这个点对两个人的价值变成一样的了。因此现在两个人的策略一定都是选择 $a+b$ 最大的点。

下面考虑一次询问怎么做。首先需要求出所有点的 $\frac{a-b}2$ 之和，这个相当于给定一个点，求所有点到它的距离之和。可以预处理每种深度的点的子树中所有点到它的距离和，然后枚举两个点的 $\text{lca}$ 在 $O(n)$ 的时间内求出答案。进一步可以使用前缀和优化至 $O(n)$ 预处理所有点的答案，这里比较简单，不再赘述。

下面需要求出两个人决策的时候所产生的所有贡献。注意到 $a,b$ 是 $O(n)$ 的，所以我们只需要关心以每一种 $a+b$ 为权值的点有多少个。进一步地，由于两个人拿同一个权值的点相当于什么也没干，所以我们实际上只关心每种权值的点个数的奇偶性。先预处理 $nxt_i$ 表示最小的满足 $a_j\equiv 0\pmod 2$ 且 $j\ge i$ 的 $j$，这个的含义是以深度为 $i$ 的点为根的子树中，最后一个有奇数个点的层是哪一层。

设 $A,B$ 的 $\text{lca}$ 为 $C$，三者深度分别为 $x,y,t$。容易发现一个点的权值可以被写成 $dis(A,B)+2d$ 的形式，其中 $d$ 是这个点到 $A-B$ 路径的距离，因此下面所有的“对答案的贡献”均指对权值 $d$ 出现次数的贡献。最后计算答案的时候用每个 $d$ 的出现次数回推到每种权值的出现次数即可。

对于 $A$ 子树内的点，深度位于 $[x,nxt_x]$ 中的点都有奇数个，所以会对区间 $[0,nxt_x-x]$ 的答案产生贡献。$B$ 子树也是同理。对于和 $A$ 的 $\text{lca}$ 在 $C$ 之下的点，枚举 $\text{lca}$ 的深度 $d$，则只有在 $a_d$ 为偶数的时候这个子树才会产生贡献（因为要排除掉包含 $A$ 的子树），子树的贡献与 $a$ 子树中的算法类似，会对答案的区间 $[1,nxt_{d+1}-d]$ 产生贡献。特别地，还有一个对 $[0,0]$ 的贡献，表示这个 $\text{lca}$ 本身。$B$ 那一侧也是类似的。$C$ 的子树比较特别，除了 $C$ 本身贡献到 $[0,0]$ 以外，需要排除掉 $0/1/2$ 棵子树，取决于 $A,B$ 是否 $=C$。如果剩余的次数个数是奇数，则会额外对答案的区间 $[1,nxt_{t+1}-t]$ 产生贡献。最后对于 $C$ 子树之外的部分，同样枚举 $\text{lca}$ 的深度 $d$，此时它本身有一个对 $[t-d,t-d]$ 的贡献，它的子树则会对 $[t-d+1,t-d+nxt_{d+1}-d]$ 产生贡献（如果 $a_d$ 为偶数的话）。

综上所述，将所有的贡献写出，总共是 $O(n)$ 次区间修改，因此需要支持对一个 $01$ 序列区间异或 $1$，最后查询整个序列。直接差分维护即可，单次复杂度 $O(n)$，总复杂度 $O(nq)$。下面有一份实现了这个暴力的代码。

这个做法如何优化呢？首先我们发现最后算答案的时候需要遍历整个序列，这个就是不可接受的，因此我们必须找到能描述答案的更好的形式。注意到求出最终的答案序列之后，我们本质上是从后往前考察所有 $1$ 的位置，假设这些 $1$ 依次在位置 $p_1>p_2>\cdots>p_k$ 位置上。特别地，如果 $k$ 为奇数则认为 $p_{k+1}=0$。这个局面产生的答案在去掉了常数之后形如 $\sum_i p_{2i-1}-p_{2i}$。注意到这意味着对整个序列做一次后缀异或和，然后新得到的序列中 $1$ 的个数就是这个式子的值。因此我们的修改和查询操作就变成了：区间异或 $1$，查询全局后缀异或和中的 $1$ 的个数。稍加讨论可以发现将区间 $[l,r]$ 异或 $1$ 对于后缀异或和序列的影响是对位置 $r,r-2,\cdots$ 异或 $1$，且对位置 $l-1,l-3,\cdots$ 异或 $1$。因此将后缀异或和序列按照下标奇偶分成两个序列，则一次操作就变成了前缀异或 $1$ 的操作，最后需要查询整个序列中 $1$ 的个数。

上面这个对操作的描述就有很多优化的空间了，例如我们可以使用线段树等数据结构做上面这个操作，然后考虑去优化操作的次数，使得不用每次询问都做那么多次操作。我们首先发现一次询问的操作分为三类：第一类是只和 $t$ 有关的操作，第二类是和 $x,y,t$ 均有关的操作，第三类是所有不在循环中的每次询问执行 $O(1)$ 次的操作。对于第三类操作，我们不需要进行优化，每次在数据结构上直接暴力做这些操作即可。下面考虑另外两种操作怎么处理。

对于第一类操作，我们的操作是对于所有 $d<t$，如果 $a_d$ 为偶数，修改区间 $[t-d+1,t-d+nxt_{d+1}-d]$。可以相当将询问离线之后从小到大枚举 $t$，则一个 $d$ 的贡献几乎和 $t$ 无关，所以这里的修改可以累加。唯一和 $t$ 有关的地方是下标，所以为了避免问题，我们将下标一起平移 $n-t$，这样这里修改的区间就变为 $[n-d+1,n-d+nxt_{d+1}-d]$。这样平移之后第二类操作的下标也要平移，但由于它们本来就和 $t$ 有关，所以平移之后也没有什么本质的影响。现在我们离线之后将询问按照 $t$ 排序，实时处理所有比当前 $t$ 更小的 $d$ 的修改，在增加 $t$ 的时候将增加的修改加入即可，总共是 $O(n)$ 次修改。

对于第二类操作，我们需要对所有 $i\in [t,x]$，如果 $a_i$ 是偶数，则修改区间 $[n-t+1,n-t+nxt_{i+1}-i]$。注意这里修改的区间已经加上了平移的偏移量。这看起来不好优化，因为每次询问的 $x,y$ 均不同，且还有下界 $t$，所以并不能动态地维护这些操作。不过我们考察 $nxt_{i+1}-i$ 的含义，可以发现在 $a_i$ 为偶数时，$nxt_{i+1}$ 就指的是下一个为偶数的 $a_j$ 的位置。因此一次修改时所有的 $i\in [t,x]$ 所修改的 $nxt_{i+1}-i$ 之和不超过 $n$。由于两个相同的 $nxt_{i+1}-i$ 操作相当于什么也没做，所以我们只关心出现次数为奇数的那些 $nxt_{i+1}-i$ 是什么。显然本质不同的 $nxt_{i+1}-i$ 只有 $O(\sqrt n)$ 个，那么出现次数为奇数的必然也是 $O(\sqrt n)$ 个。因此我们可以预处理所有前缀的出现次数为奇数的 $nxt_{i+1}-i$ 有哪些，然后在修改区间 $[t,x]$ 时只需要把这两个大小为 $O(\sqrt n)$ 的数组归并之后做修改即可。求出所有数组以及归并都只需要 $O(n\sqrt n)$ 的时间，而这样单次询问一共需要 $O(\sqrt n)$ 次操作。

综合上述所有情形，现在问题变成了，$O(n\sqrt n)$ 次区间异或 $1$ 操作，$O(n)$ 次查询全局 $1$ 的个数。如果使用线段树维护，复杂度为 $O(n\sqrt n\log n)$，不能通过。可以想到平衡复杂度，但很难有 $O(1)$ 修改 $O(\sqrt n)$ 查询全局和的数据结构，所以还需要一些别的观察。

注意到我们的瓶颈 $O(n\sqrt n)$ 次操作并不是没有规律的。单次询问的 $O(\sqrt n)$ 次操作所操作的区间的左端点是一样的，且在询问结束之后这些操作还要被撤回。先把左端点的贡献单独拿出来当作 $O(1)$ 次操作，则此时相当于在做 $O(\sqrt n)$ 次前缀修改的操作。如果我们修改的位置分别为 $p_1>p_2>\cdots$，则可以看作是修改区间 $[p_2+1,p_1],[p_4+1,p_3]$ 等等。这样这些区间就全部都是相离的。由于我们只关心最后的全局和，所以可以直接考虑每次修改对答案的贡献。显然这些相离的操作之间互相不会产生影响，所以只需要能够查询区间内 $1$ 的个数，就可以将瓶颈从修改变成查询了。

因此现在问题变成了 $O(n)$ 次区间异或 $1$，$O(n\sqrt n)$ 次查询区间 $1$ 的个数。这个是存在 $O(\sqrt n)$ 修改 $O(1)$ 查询的方法的。考虑分块，然后对每个块维护在这个块前面的 $1$ 的个数，并对每个位置维护在块内它前面的 $1$ 的个数。修改时整块修改可以直接扫一遍所有块，在修改的块上打标记并更新后面块维护的值。对于散块修改，暴力重新求出块内的前缀和，然后用这个块的前缀和更新后面的块。查询时直接用当前位置块的前缀和和块内的前缀和即可 $O(1)$ 回答一个前缀的答案。

这样就解决了这个问题，复杂度 $O((n+q)\sqrt n)$。下面的代码经过了部分常数优化，有一些式子变形比较大。