P9099 题解

qiuzx · 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)。下面的代码经过了部分常数优化，有一些式子变形比较大。