官方题解（中文整理）

基于 Agastya Goel 的官方题解整理。

关键观察

先观察一头奶牛从队首回到队首需要多久。

如果一头奶牛在时刻 \(t\) 前位于队首，那么在时刻 \(t\) 后它会被移到位置 \(\left\lfloor \frac{t}{2} \right\rfloor\)。之后它每一步最多前进一格，所以它最早要到时刻：

\(t + 1 + \left\lfloor \frac{t}{2} \right\rfloor\)

才能再次回到队首。这个值至少是 \(\frac{3}{2}t\)。

因此，一头奶牛在前 \(T\) 个时刻内能来到队首的次数只有 \(O(\log T)\) 级别。这说明两种询问都可以只模拟很少的“关键跳转”。

询问 1：给定奶牛，求位置

设函数 \(f(i,t)\) 表示奶牛 \(i\) 在时刻 \(t\) 之后的位置。

有如下规律：

• 奶牛 \(i\) 要到时刻 \(2i\) 才会第一次开始移动
• 若在某个时刻前它位于位置 \(p>0\)，那么之后会连续前进，直到再过 \(p\) 步回到队首
• 若它在某个时刻前位于队首，那么下一步会被送到位置 \(\left\lfloor \frac{t}{2} \right\rfloor\)

于是只需要在“回到队首”与“从队首跳到中间”这两类事件之间跳跃模拟即可。由于这样的循环次数只有 \(O(\log t)\)，所以单次询问复杂度也是 \(O(\log t)\)。

询问 2：给定位置，求奶牛

设 \(c(p,t)\) 表示时刻 \(t\) 之后位于位置 \(p\) 的奶牛编号。

如果把所有奶牛都看成一开始就在一条无限长队列里，那么初始有：

\(c(p,0)=p\)

根据队列的演化规则，可以得到三条转移：

• \(c\!\left(\left\lfloor \frac{t}{2} \right\rfloor, t\right)=c(0,t-1)\)
• 当 \(p > \left\lfloor \frac{t}{2} \right\rfloor\) 时，\(c(p,t)=p\)
• 当 \(p < \left\lfloor \frac{t}{2} \right\rfloor\) 时，\(c(p,t)=c(p+1,t-1)\)

第三条转移如果每次只退一步会太慢，因此需要一次跳多步。我们希望找到尽可能大的 \(\Delta\)，使得：

\(c(p,t)=c(p+\Delta,\,t-\Delta)\)

为了让这 \(\Delta\) 次都合法，需要在最后一步之前仍满足：

\(p+\Delta-1 < \left\lfloor \frac{t-\Delta+1}{2} \right\rfloor\)

取

\(\Delta = \left\lfloor \frac{t-2p}{3} \right\rfloor\)

总是安全的。这样每次都能大幅缩小参数，只有在接近边界时才需要补几次一步一步的转移，因此总复杂度仍是 \(O(\log t)\)。

复杂度

两类询问都可以在 \(O(\log t)\) 时间内解决，总复杂度为 \(O(Q \log t)\)。