题解：P10198 Infinite Adventure P

\(\text{Link}\)

题意

给定 \(n\) 个数组 \(c_{i,0\dots t_i-1}\)，其中 \(t_i\) 为 \(2\) 的幂。有 \(q\) 次询问，每次询问给出三个参数 \(x,T,\Delta\)，接下来会执行 \(\Delta\) 次 \(x\gets c_{x,T\bmod t_x},T\gets T+1\)，求出最终的 \(x\)。

\(n,\sum t\le 10^5\)，\(q\le 5\times 10^4\)。

题解

令 \(n=\sum t\)，\(v=\max\Delta\)。

从一点开始走若干步到达的点提示使用倍增。

我们的状态数不能太多，于是一个想法是设 \(f_{i,j,k}\) 表示现在在点 \(i\)，当前时间 \(\bmod\ t_i\) 等于 \(j\)，走 \(2^k\) 步到达的点。

此时一个问题是如果跳到一个 \(t_u>t_i\) 的点 \(u\)，维护的信息不足以得知当前时间 \(\bmod\ t_u\) 的值。注意到 \(t_i\) 只有 \(\log n\) 种，即我们在一条路径上最多遇到 \(\log n\) 次这种情况。于是我们将此种情况下的 \(f_{i,j,k}\) 定义为在这 \(2^k\) 步中遇到的第一个 \(t_u>t_i\) 的点 \(u\)，还需再维护 \(g_{i,j,k}\) 表示在这个 \(u\) 之前已经走了几步了。

预处理与单次询问均可模拟：从高至低枚举每一位，不断跳直到该位为 \(0\)，每一位至多只会跳 \(\log n\) 次。时间复杂度为 \(O(n\log n\log^2v+q\log n\log v)\)，无法通过。

考虑复杂度瓶颈为预处理部分，我们在特殊情况中经过了形如 \(i\to u\to v\) 且 \(t_u<t_v<t_i\) 这样的路径，这造成了很大的复杂度开销，我们希望每一次跳到的点 \(u\) 对应的 \(t_u\) 均为路径上的前缀最大值，这样一条任意长的路径也只需要跳 \(\log n+\log v\) 次即可跳完。

考虑令 \(f_{i,j,k}\) 为在时间为 \(j\pmod{t_i}\) 时从点 \(i\) 开始不断走直到经过了 \(2^k\) 个使得 \(t_u=t_i\) 的点 \(u\) 或到达一个使得 \(t_u>t_i\) 的点 \(u\)，此时到达的点。相应地有 \(g_{i,j,k}\) 表示这条路径的长度。

预处理时先从小到大枚举 \(v\)，对所有 \(t_i=2^v\) 的 \(i\) 求出所有 \(f_{i,j,k}\)。重点为求出 \(f_{i,j,0}\)，从 \(c_{i,j}\) 开始不断向其后第一个 \(t\) 比自身大的跳即可。

询问时先不断向大跳直到达到路径上 \(t\) 的最大值，此后跳过所有 \(t\) 值为最大值的点即可减小最大值，显然我们只能减少 \(\log n\) 次。

总时间复杂度 \(O(n\log v+q\log n\log v)\)，可以通过。