CF1060G 题解

· · 题解

NOIP 模拟赛 T2。很厉害的题。

想象数轴上 a_1, a_2, \ldots, a_n 位置上各有一个洞，每个非负整数位置上有一个点。

每次操作相当于，对于每个点，如果它刚好位于一个洞，那么它会掉进去；否则设它的位置为 p，位置在它前面的洞有 t 个，那么这个点的位置变成 p - t。容易发现每时刻每个点的位置互不相同。

一次询问 (x, k) 相当于，进行 k 次操作后，找到数轴上位置为 x 的点，求它进行所有操作前的位置。

单点的移动没有很好的性质。考虑一段连续点的移动。比如极远处 L = 10^{18} 有一段连续点 [L, L + n - 1]；那么容易发现这些点不重不漏地经过 [a_1, L + n - 1] 的位置。并且每一时刻连续点都是一段连续的区间。

发现对于一个 [a_i, a_{i + 1}) 段内的移动，连续点的区间 [L, L + i - 1] 只会重复地进行 L \gets L - i 的变化，直到连续点覆盖了 a_i。那么我们只需要维护当连续点的区间覆盖了一个洞时连续点的变化（有哪些点掉洞里了）。

对于一个询问 (x, k)，设在 t 时刻连续点覆盖了 x，就相当于求它 t - k 时刻的位置。

那么每个询问都可以被转化成，初始位于 L + x 的点，求它 k 时刻的位置。询问全部离线下来按 k 从小到大排序，直接模拟一遍即可。

使用树状数组维护初始 [L, L + n - 1] 的连续点哪些掉洞里了。

时间复杂度 O((n + m) \log n)。

code