自动搬运

查看原文

来自洛谷，原作者为

	寻逍遥2006 晓看天色暮看云，行也思君，坐也思君；春赏百花冬赏雪，醒也思卿，梦也思卿

搬运于2025-08-24 22:44:26，当前版本为作者最后更新于2024-08-25 22:04:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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 可以直接选择这组匹配中的较大点，显然这不是 A 的最优策略。
• 如果选择的点不在任何匹配中，由于已经是最大匹配了，那么 B 选择的点一定在匹配之中，如果其选择的是较大点，那么这不是 A 的最优策略；如果其选择的是较小点，发现将较小点原来的匹配改成这一次 A 和 B 选择的这一组匹配，匹配权值不变，仍然是一组最大权匹配。

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)$，其中前者为扩展欧几里得的复杂度，后者为线段树的复杂度。

代码