题解：P8995 [北大集训 2021] 随机数据

· · 题解

P8995 [北大集训 2021] 随机数据

首先考虑答案到底是要算什么。

我们可以明确 B 在可以选择的情况下必然会选择能选的中较大的。因为 B 没有办法做到故意给 A 留下物品来让自己取到的物品更优，因为 A 完全可以当作 B 留下的物品已经被取了，直到 B 选择了他之前没有选择的物品，或者在其他物品都被选择了的情况下 A 将其选择。

我们假设 d=1，发现可以将问题放在环上处理，在 (i,(i+1)\bmod n) 之间连边。原题中操作变成了：当 A 选择了一个物品之后，B 可以选择一个和 A 选择的物品有直接连边的物品。

对于边 (a,b)，如果 A 选择了 a,b 中的一个，则 B 会也会取到另外一个，显然 A 会选择较大的那一个。发现这个过程类似匹配。所以我们记边 (a,b) 的权值为 \min\{v_a,v_b\}。那么我们发现，答案就是这张图的最大权匹配。

证明可以考虑反证法，如果 A 不选择最大权匹配中的一组匹配的较大点：

B 的讨论是类似的。

而由于这是环上的最大权匹配，先断环为链，我们可以直接维护序列的答案：

记 be 和 en 为链上的第一个物品的价值和最后一个物品的价值，num_{0/1,0/1} 表示第一个物品是/否被匹配了，最后一个武平是/否被匹配了的情况下的最大权匹配的权值是多少。

这个信息是可以快速合并的，而将序列拼回环也是容易的，只需要讨论第一个物品和最后一个物品是否会形成匹配即可。

如果 d\neq 1，发现我们仍可以连边 (i,(i+d)\bmod n)，问题仍然是最大权匹配。由于这张图是由 g=\gcd(d,n) 个环构成的，所以可以对于每一个环去求答案。

发现让一个物品不可用等价于让这个物品的权值变成 0，所以修改也是很好维护的。

这样，我们直接使用线段树维护信息，就可以做到 O(n+q\log n) 的时间复杂度，获得 30 分。

考虑如何把问题拓展到 n 更大的情况。

我们可以借助动态开点线段树的思想，其实修改我们只关注那线段树上的 O(\log n) 个节点，其余节点由于没有修改，所以信息都是确定的，就是原序列上对应区间的信息，那么我们的问题就转换成了如何快去的求原序列上一区间的信息。

先简化这个问题，考虑如何求出整个序列的信息。

我们不妨考虑所有 i\bmod g=0 的点构成的序列。

这个环上的物品依次是原序列中的第 0,d,2d \dots n-d 个物品，其中第 i 个物品（i=0,1,\dots \dfrac{n}{g}-1）在原序列中的下标为 (d\times i)\bmod n。

那么对应到输入的 w 序列中，就是第 ((d\times i)\bmod n)\bmod m 个物品。

发现有两层取模，并不好处理，但是注意到 (d\times i)\bmod n=d\times i-n\left\lfloor\dfrac{d\times i}{n}\right\rfloor，那么在 w 序列中对应的下标就是 (d\times i-n\left\lfloor\dfrac{d\times i}{n}\right\rfloor)\bmod m。

发现有 \left\lfloor\dfrac{d\times i}{n}\right\rfloor 的结构，类似于 \left\lfloor\dfrac{ai+b}{c}\right\rfloor，而这类东西，我们可以尝试用万能欧几里得算法来维护。

如果你没有学过万能欧几里得算法，可以参考 ix35 的博客。

那我们考虑 U 操作和 R 操作分别对应什么。

我们可以同时维护 m 个信息，表示从 w_i 开始的序列的信息。我们记第 i 个信息只维护了 w_i 一个数构成的序列的信息为基础单位。

那么 U 操作就是让维护的信息向左循环位移 n 位，让 w_i 接下来加上的数变成 w_{(i-n)\bmod m}；R 操作是让维护的信息向右循环位移 d 位（作用和 U 操作同理），同时和一个基础单位合并。

由于万能欧几里得算法本身的复杂度是 O(\log n) 的，所以在合并的过程中只会出现 O(\log n) 个不同的信息，所以维护的时间复杂度是 O(m\log n) 的。

现在考虑如何获得这个序列的其中一个子区间序列的信息。

由于在万能欧几里得算法中的所有合并都是二元合并，所以将整个合并过程展开，会得到一个深度是 O(\log n) 个二叉树，那么获取区间信息就是容易的：我们只需要像线段树一样进行区间查询就可以了。

解决了上面个两个问题之后，其实这个问题就已经解决了大半了。剩下的就是一些细节问题：比如如果我们从每一个环 <g 的那个点的前端断开，那么 x 会对应到哪一个环的哪一个位置。

首先它和第 r=x_i\bmod g 个物品在同一个序列，而它在这个序列中的第几个元素：那就是要找到最小的非负整数 t，使得 d|(x_i-r+nt)，也就是找 nt\equiv r-x_i\pmod d。

使用扩展欧几里得算法解出 g=an+bd 的一组解，其中 a\ge 0，如果 \dfrac{r-x_i}{g}=t'，那么就有 nt\equiv gt'\pmod d。容易得到一组解为 t=at'，要求 t 最小，那么 t 就等于 (at'\bmod \dfrac{d}{g}) 。那么 x_i 在序列中就是第 \dfrac{x_i-r+n(a\dfrac{r-x_i}{g}\bmod \dfrac{d}{g})}{d}+1 个数。

还有细节就是 g 本身可能很大，所以我们不能够对于每一个环在万能欧几里得算出的答案，所以我们考虑对于第一个物品为 w_i 的所有序列是完全相同的，共有 \left\lfloor\dfrac{g}{m}\right\rfloor+[i<(g\bmod m)] 个。所以可以枚举 i=0,1\dots m-1，计算出以 w_i 开头的方案的权值。然后对于每一个修改，差分计算出它对于答案的修改。

时间复杂度为 O(m\log n+q\log n)，其中前者为扩展欧几里得的复杂度，后者为线段树的复杂度。

代码