题解：CF1060G Balls and Pockets

ZnPdCo · 2025-11-26 08:05:30 · 题解

尝试考察一个极远的数值区间 [L,L+n-1]（不妨令 L=10^{18}），用线段树维护这 n 个数值当前所在的位置，记作 g。我们每次操作一遍会有什么影响？

如果 g_L>a_n，此时操作一次会令 g 中每个元素的值减去 n（相当于 [L,L+n-1] 中每个数的对应位置向前移动 n 步）。

而如果 g_L\le a_n\le g_{L+n-1}，且 g_L>a_{n-1}。此时操作一次会使得 a_n 这个位置上的数被删掉。二分出 a_n 这个位置对应的数值 x，那么在线段树 g 上，<x 的数的位置会减去 n-1，而 >x 的数的位置会减去 n。为了方便，我们不妨令 x 本身的位置也减去 n-1，这样的话 x 就和 x+1 重叠了，它们位置相同了。我们只需要在线段树二分的时候取出最后一个满足条件的数，就可以实现类似于删除 x 的效果。

上面的过程在干什么？我们先定义「向前移动」操作表示将 g 中每个数减去 n。而当 g_L>a_n 时，在下一次「向前移动」前，我们需要先把被 a 覆盖的位置扣掉。我们就二分出 g_x=a_n，将 [x+1,L+n-1] 的 g 减 1，然后将 n\gets n-1。后面再进行「向前移动」操作的时候结果也是正确的（原谅我的语言表达能力，这里或许有一些难懂，但这里其实爱怎么处理怎么处理，先继续下去吧）。

我们发现如果 g_L 同一时间覆盖了多个 a 也是相同的。假如恰好覆盖了 a_{n-1} 和 a_n（设二分出的结果是 x,y），此时 [y+1,L+n-1] 的 g 减去 n，[x+1,y] 减去 n-1，[L,x] 减去 n-2。

上面的过程在干什么？我们在下一次「向前移动」之前，如果发现 g_L 覆盖了 a_n，就二分出 g_x=a_n，将 [x+1,L+n-1] 的 g 减去 1，然后将 n\gets n-1，然后继续判断 g_L 是否覆盖新的 a_n，如果是则重复上述过程。

这里类似于一个双指针。此时我们不禁想，这个双指针到底是否正确，是否会出现某个 a_n，处理完 a_n 的情况后，新的 [g_L,g_{L+n-1}] 还是包含 a_n？

实际上并不存在，这是因为：

• 数值 [L,L+n-1] 不断向前移动，它们所有时刻的所有位置构成的集合不重，且是 [a_1,L+n-1]。

这是因为在 [L,L+n-1] 的位置不包含 a_n 时，显然是不断向前移动 n 步的，不会重复。而当它们遇到一个 a_n 后，二分出 x，是 [L,x-1] 的位置向前移动 n 步，[x+1,L+n-1] 的位置向前移动 n 步，删掉 a_n 对应的数（不要忘了上面只是将 a_n 对应的数和 a_{n+1} 对应的数重叠在一起方便处理，实际上它是要被删掉的）。