A7114. [USACO26JAN1] Lineup Queries S
编程题
普及+/提高
知识点
题目描述
一开始只有一头奶牛，编号为 $0$，位于下标 $0$。
接下来进行若干轮操作。对于第 $x$ 轮（$x$ 从 $1$ 开始），令
$$ m=\left\lfloor \frac{x}{2}\right\rfloor. $$
这一轮依次执行：
1. 将当前位于下标 $0$ 的奶牛移动到下标 $m$。
2. 原本处于下标区间 $[1,m]$ 的奶牛整体向前移动一格（下标都减 $1$）。
3. 新建一头奶牛，编号为 $x$，并放到下标 $x$。
可以证明：第 $t$ 轮结束后，恰好有 $t+1$ 头奶牛，分别位于下标 $0,1,2,\dots,t$。
你需要回答 $q$ 个询问，每个询问给出一个轮数 $t$ 与一个参数 $x$：
- 询问 1：第 $t$ 轮结束后，编号为 $x$ 的奶牛位于哪个下标？
- 询问 2：第 $t$ 轮结束后，下标为 $x$ 的位置上是哪一头奶牛（输出其编号）？
接下来进行若干轮操作。对于第 $x$ 轮（$x$ 从 $1$ 开始），令
$$ m=\left\lfloor \frac{x}{2}\right\rfloor. $$
这一轮依次执行：
1. 将当前位于下标 $0$ 的奶牛移动到下标 $m$。
2. 原本处于下标区间 $[1,m]$ 的奶牛整体向前移动一格（下标都减 $1$）。
3. 新建一头奶牛，编号为 $x$，并放到下标 $x$。
可以证明：第 $t$ 轮结束后，恰好有 $t+1$ 头奶牛，分别位于下标 $0,1,2,\dots,t$。
你需要回答 $q$ 个询问，每个询问给出一个轮数 $t$ 与一个参数 $x$：
- 询问 1：第 $t$ 轮结束后，编号为 $x$ 的奶牛位于哪个下标？
- 询问 2：第 $t$ 轮结束后，下标为 $x$ 的位置上是哪一头奶牛（输出其编号）？
输入格式
第一行包含一个整数 $q$，表示询问个数。
接下来 $q$ 行，每行包含三个整数 $op,t,x$：
- 若 $op=1$，表示询问 $1$；
- 若 $op=2$，表示询问 $2$。
接下来 $q$ 行，每行包含三个整数 $op,t,x$：
- 若 $op=1$，表示询问 $1$；
- 若 $op=2$，表示询问 $2$。
输出格式
对于每个询问输出一行一个整数表示答案。
输入输出样例
输入 #1
4 1 2 1 2 2 0 2 4 2 1 4 0
输出 #1
0 1 0 2
说明/提示
## 数据范围
- $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$
- $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$