题解：P14617 [2019 KAIST RUN Fall] Hilbert' s Hotel

· · 题解

本题只有两种修改操作，可以将每种修改操作看成对有已有的编号进行修改和加入新的编号：

  1. 一类修改：来了 k 个人，所有已有团队成员的编号都会加 k，新来的团队第 i 个人编号为 i-1；
  2. 二类修改：来了无限个人，所有已有团队成员的编号都会变为原来的 2 倍，新来的团队第 i 个人编号为 2i-1。

先考虑前一种询问。设当前总共进行了 n 次修改（也就是题面中的 G-1），第 i 次修改对于第 0\sim i-1 次修改所加入的编号的影响可以看成一个一次函数 f_i(x)=2x 或 f_i(x)=x+k。当询问第 a 个团队第 b 个人此时的编号时，容易求出这个人刚加入时的编号 c，那么答案即为 f_n(f_{n-1}(\dots f_{a+1}(c)))。

这可以直接用数据结构（如线段树）维护做到 O(\log Q) 查询，但由于本题的特殊性，可以做到 O(1) 查询。记录 f 的前缀复合 F_i(x)，满足 F_0(x)=0，且对于 i\geq 1 有 F_i(x)=f_i(F_{i-1}(x))，那么容易发现本题中一定有 F_i(x)=2^{k_i}x+b_i。而要求的 g(x)=f_n(f_{n-1}(\dots f_{l+1}(x)))，就是满足 g(F_a(x))=F_n(x) 的一次函数 g，即 k_g(2^{k_a}x+b_a)+b_g=2^{k_n}x+b_n，可得 k_g=2^{k_n-k_a},b_g=b_n-k_gb_a。故这一部分复杂度为线性。

再考虑另一种询问。首先可以得到暴力做法，依次遍历第 n,n-1,\dots,1 种修改，设当前查询编号为 x，则：

  1. 这次修改对应 k 为 0，则如果 x 为奇数就找到答案，否则令 x\leftarrow \frac{x}{2}；
  2. 这次修改对应 k 不为 0，则如果 x<k 就找到答案，否则令 x\leftarrow x-k。

考虑优化上述过程。注意到如果 x 变为 0，则答案一定为剩下的修改中最后一次一类修改（不存在则为 0），这容易做到 O(1) 查询。同时，x 在遇到 O(\log x) 二类修改后就会变为 0。所以可以考虑倒着遍历每种二类修改，直到 x=0。而相邻两种二类修改之间的一类修改容易用前缀和判断是否能完整跳过（即这些修改的 k 之和是否大于 x），如果不能全部跳过则答案就在这段中，二分即可找到。这部分复杂度为 O(\log x+\log Q)。

总复杂度 O(Q(\log x+\log Q))，瓶颈在于第二种询问。