A7114 | [USACO26JAN1] Lineup Queries S

数据范围

• $1\le q\le 2\times 10^5$；
• $0\le t\le 10^{18}$；
• 对于任意询问，保证 $0\le x\le t$；
• 需要注意读入效率。



样例解释





第 $0$ 轮（初始）


只有编号为 $0$ 的奶牛在下标 $0$：
$$ [0] $$

---



第 $1$ 轮


本轮 $x=1$，令
$$ m=\left\lfloor \frac{1}{2}\right\rfloor=0. $$

1. 将下标 $0$ 的奶牛（编号 $0$）放到下标 $m=0$（位置不变）。
2. 原本处于区间 $[1,m]=[1,0]$ 的奶牛整体前移一格（该区间为空，无变化）。
3. 新建编号为 $1$ 的奶牛放到下标 $1$。

因此第 $1$ 轮结束后序列（下标 $\to$ 编号）为：
$$ [0,\,1] $$

---



第 $2$ 轮


本轮 $x=2$，令
$$ m=\left\lfloor \frac{2}{2}\right\rfloor=1. $$

第 $1$ 轮结束时序列为 $[0,1]$，即下标 $0$ 是编号 $0$，下标 $1$ 是编号 $1$。

1. 将下标 $0$ 的奶牛（编号 $0$）移动到下标 $m=1$。
2. 原本处于区间 $[1,m]=[1,1]$ 的奶牛（编号 $1$）整体前移一格，变到下标 $0$。
3. 新建编号为 $2$ 的奶牛放到下标 $2$。

因此第 $2$ 轮结束后序列为：
$$ [1,\,0,\,2] $$

由此：
• 询问 $1$（$t=2$）：编号 $1$ 在下标 $0$，输出 $0$
• 询问 $2$（$t=2$）：下标 $0$ 上是编号 $1$，输出 $1$

---



第 $3$ 轮


本轮 $x=3$，令
$$ m=\left\lfloor \frac{3}{2}\right\rfloor=1. $$

第 $2$ 轮结束时序列为 $[1,0,2]$。

1. 将下标 $0$ 的奶牛（编号 $1$）移动到下标 $m=1$。
2. 原本处于区间 $[1,1]$ 的奶牛（编号 $0$）整体前移一格，变到下标 $0$。
3. 新建编号为 $3$ 的奶牛放到下标 $3$。
并且原来下标 $2$ 的奶牛（编号 $2$）不在区间 $[1,1]$ 中，因此保持在下标 $2$。

因此第 $3$ 轮结束后序列为：
$$ [0,\,1,\,2,\,3] $$

---



第 $4$ 轮


本轮 $x=4$，令
$$ m=\left\lfloor \frac{4}{2}\right\rfloor=2. $$

第 $3$ 轮结束时序列为 $[0,1,2,3]$。

1. 将下标 $0$ 的奶牛（编号 $0$）移动到下标 $m=2$。
2. 原本处于区间 $[1,2]$ 的奶牛（编号 $1$ 和编号 $2$）整体前移一格：
- 编号 $1$ 从下标 $1$ 变到下标 $0$
- 编号 $2$ 从下标 $2$ 变到下标 $1$
3. 新建编号为 $4$ 的奶牛放到下标 $4$。
并且原来下标 $3$ 的奶牛（编号 $3$）不在区间 $[1,2]$ 中，因此保持在下标 $3$。

因此第 $4$ 轮结束后序列为：
$$ [1,\,2,\,0,\,3,\,4] $$

由此：
• 询问 $2$（$t=4$）：下标 $2$ 上是编号 $0$，输出 $0$
• 询问 $1$（$t=4$）：编号 $0$ 在下标 $2$，输出 $2$