官方题解（中文整理）

基于 Alexander Wang 的官方题解整理。

先定义单点位置函数

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

奶牛 \(i\) 在时刻 \(i\) 加入队列，初始位置是 \(i\)。在区间 \(i \le t \le 2i-1\) 内，它不会移动，因此：

\(f(i,t)=i \qquad (i \le t \le 2i-1)\)

当 \(t \ge 2i\) 时，它每一步要么向前移动一格，要么如果它恰好在队首，就会被送到位置 \(\left\lfloor \frac{t}{2} \right\rfloor\)。

子任务 1：直接递推

对于小数据，直接按照定义递推 \(f(i,t)\) 即可：

\(f(i,t)= \begin{cases} i, & i \le t \le 2i-1 \\ f(i,t-1)-1, & f(i,t-1)\neq 0,\ t \ge 2i \\ \left\lfloor \frac{t}{2} \right\rfloor, & f(i,t-1)=0,\ t \ge 2i \end{cases}\)

随后枚举 \(i \in [l_1,r_1]\)，统计其中有多少满足 \(l_2 \le f(i,t) \le r_2\) 即可。

子任务 2：单头奶牛

如果只需要求一头固定奶牛的位置，那么可以利用“回到队首的时刻”做跳跃。

当奶牛 \(i\) 在某个时刻 \(t'\) 后位于队首时，下一步它会被送到位置：

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

之后它会连续前进，直到再经过这么多步后重新回到队首。因此下一次回到队首的时刻是：

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

令：

• \(t_{i,0}=2i-1\)
• \(t_{i,1}=3i-1\)
• \(t_{i,j}=t_{i,j-1}+1+\left\lfloor \frac{t_{i,j-1}+1}{2} \right\rfloor \quad (j \ge 2)\)

那么对所有 \(j>0\)，都有：

\(f(i,t_{i,j})=0\)

并且当 \(t_{i,j-1}<t\le t_{i,j}\) 时：

\(f(i,t)=t_{i,j}-t\)

由于 \(t_{i,j}\) 至少按 \(\frac{3}{2}\) 的倍率增长，而 \(\left(\frac{3}{2}\right)^{110} > 10^{18}\)，所以每头奶牛只需考虑最多 \(110\) 个这样的关键时刻。

正解：把区间计数拆成两类

对于一个询问，我们要求的是满足：

\(l_1 \le i \le r_1,\qquad l_2 \le f(i,t) \le r_2\)

的奶牛数量。

按奶牛 \(i\) 在时刻 \(t\) 是否已经开始循环移动，分成两类。

第一类：\(t \le 2i-1\)

这等价于 \(i > \frac{t}{2}\)。此时奶牛 \(i\) 还没有真正移动过，位置就是自己：

\(f(i,t)=i\)

因此只需统计区间：

\(i \in [l_1,r_1] \cap [l_2,r_2] \cap \left[\left\lfloor \frac{t}{2} \right\rfloor+1,\infty\right)\)

的大小即可。

第二类：\(t \ge 2i\)

这时一定存在某个 \(j \in [1,110]\)，使得：

\(t_{i,j-1}<t\le t_{i,j}\)

并且：

\(f(i,t)=t_{i,j}-t\)

因此对固定的 \(j\)，需要统计满足下列条件的 \(i\)：

• \(l_1 \le i \le r_1\)
• \(i \le \left\lfloor \frac{t}{2} \right\rfloor\)
• \(l_2+t \le t_{i,j} \le r_2+t\)
• \(t_{i,j-1} \le t-1\)

关键在于如何把关于 \(t_{i,j}\) 的限制转成对 \(i\) 的区间限制。

反推 \(t_{i,j} \le x\)

固定 \(j\) 后，\(t_{i,j}\) 随 \(i\) 单调递增，因此满足 \(t_{i,j}\le x\) 的 \(i\) 一定形如 \(i \le A\)。

当 \(j=1\) 时：

\(t_{i,1}=3i-1\)

所以：

\(t_{i,1}\le x \iff 3i-1\le x\)

当 \(j \ge 2\) 时，由递推式：

\(t_{i,j}=t_{i,j-1}+1+\left\lfloor \frac{t_{i,j-1}+1}{2} \right\rfloor\)

可化成：

\(t_{i,j}\le x \iff t_{i,j-1}\le \left\lfloor \frac{2x-2}{3} \right\rfloor\)

定义：

\(g(x)=\left\lfloor \frac{2x-2}{3} \right\rfloor\)

那么就有：

\(t_{i,j}\le x \iff t_{i,1}\le g^{j-1}(x) \iff 3i-1 \le g^{j-1}(x)\)

这就把所有条件都变成了对 \(3i-1\) 的上下界限制，从而能在 \(O(1)\) 时间内求出固定 \(j\) 的贡献。

具体实现

对每个询问，预处理三个长度约为 \(110\) 的数组：

• \(\mathrm{inv1}[j]=g^{j-1}(t-1)\)
• \(\mathrm{inv2}[j]=g^{j-1}(l_2+t-1)\)
• \(\mathrm{inv3}[j]=g^{j-1}(r_2+t)\)

于是固定 \(j\) 时，对应的条件等价于：

• \(3i-1 \le \mathrm{inv3}[j]\)
• \(3i-1 > \mathrm{inv2}[j]\)
• \(3i-1 \le \mathrm{inv1}[j-1]\)

再与 \(l_1 \le i \le \min(r_1,\lfloor t/2 \rfloor)\) 取交，就得到一个整数区间，可以直接统计大小。

枚举 \(j=1 \dots 110\)，把所有贡献加起来，再加上第一类的贡献即可。

复杂度

每个询问只需处理常数个长度 \(110\) 的数组，因此总复杂度为：

\(O(110Q)\)

可以通过全部数据。