题解：CF1060G Balls and Pockets

尝试考察一个极远的数值区间 $[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_n$ 时，显然是不断向前移动 $n$ 步的，不会重复。而当它们遇到一个 $a_n$ 后，二分出 $x$，是 $[L,x-1]$ 的位置向前移动 $n$ 步，$[x+1,L+n-1]$ 的位置向前移动 $n$ 步，删掉 $a_n$ 对应的数（不要忘了上面只是将 $a_n$ 对应的数和 $a_{n+1}$ 对应的数重叠在一起方便处理，实际上它是要被删掉的）。

$x+1$ 的位置是 $x-1$ 的位置加 $2$，而 $x-1$ 的位置减 $n$，$x+1$ 的位置减 $n-1$，它们这么操作后变成了一个长度为 $n-1$ 的连续段，之后每次都会减去 $n-1$， 变成了子问题。归纳证明出它们构成的位置结合不重不漏覆盖 $[a_1,L+n-1]$。

于是我们可以双指针求出每个位置 $x_i$ 在经过 $t_i$ 轮之后的数是 $w_i$。但这里 $t_i$ 不是我们能够控制的，且一定不等于 $d_i$，不过拜 $L$ 是极大值所赐，$t_i>d_i$。

设 $f(x)$ 表示经过一轮操作后 $x$ 这个位置上的值是什么，相当于我们已经得知 $f^t(x)=w$ 了。

不妨考虑复合上 $f^{d-t}$ 这个函数，而因为 $t>d$，也可以看作复合上 $(f^{-1})^{t-d}$ 这个函数。$f^{-1}$ 是什么意思：经过一轮操作后值 $x$ 在哪个位置。

所以我们还需要计算 $(f^{-1})^v(w)$，此处 $w$ 一定是 $[L,L+n-1]$ 中的数（因为 $w$ 就是这么得来的）。

我们重复上述模拟，维护数值 $[L,L+n-1]$ 所在的位置，然后达到 $v$ 轮后就处理一下 $w$ 所在位置，因为 $t-d<t$，而在 $t$ 时刻 $w$ 还能作为上一次能够求出的东西，说明 $t$ 时刻 $w$ 还没有被删掉，而 $t-d$ 时刻 $w$ 肯定还没被删掉。所以一定可以求出 $w$ 所在的位置。

求出来的就是答案。注意请特判一下 $x<a_1$ 的情况，因为 $[L,L+n-1]$ 覆盖的值只能到 $a_1$ 之后，前面是覆盖不到的，所以不能求出一个有效的 $t$ 和 $w$。