P14977 [USACO26JAN1] Lineup Queries S
题目描述
有一队奶牛，初始时（即时刻 $t = 0$）只有奶牛 $0$ 在位置 $0$（这里，一头奶牛在位置 $k$ 表示它前面有 $k$ 头奶牛）。在时刻 $t$（$t=1,2,3,\dots$），位置 $0$ 的奶牛移动到位置 $\lfloor t/2\rfloor$，位置 $1\dots \lfloor t/2\rfloor$ 上的每头奶牛向前移动一个位置，并且奶牛 $t$ 加入到队列的末尾（位置 $t$）。
回答 $Q$（$1\le Q\le 10^5$）个独立的查询，每个查询属于以下两种类型之一：
1. 在时刻 $t$ 刚结束时，奶牛 $c$ 在什么位置（$0\le c\le t\le 10^{18}$）？
2. 在时刻 $t$ 刚结束时，位置 $x$ 上是哪头奶牛（$0\le x\le t\le 10^{18}$）？
输入格式
第一行包含 $Q$，表示查询的数量。
接下来的 $Q$ 行，每行包含三个整数，指定一个查询，格式为 "$1$ $c$ $t$" 或 "$2$ $x$ $t$"。
输出格式
将每个查询的答案输出在单独一行。
说明/提示
不同时刻刚结束时的队列排列：
```none
t = 0 | 0
t = 1 | 0 1
t = 2 | 1 0 2
t = 3 | 0 1 2 3
t = 4 | 1 2 0 3 4
t = 5 | 2 0 1 3 4 5
t = 6 | 0 1 3 2 4 5 6
t = 7 | 1 3 2 0 4 5 6 7
t = 8 | 3 2 0 4 1 5 6 7 8
t = 9 | 2 0 4 1 3 5 6 7 8 9
```
在 $t=9$ 刚结束时，奶牛 $4$ 的位置是 $2$，而位置 $2$ 上的奶牛是 $4$。
---
- 输入 $3$：$Q\le 1000, t\le 100$
- 输入 $4$：$t\le 5000$
- 输入 $5$-$8$：所有查询均为类型 1。
- 输入 $9$-$12$：所有查询均为类型 2。
翻译由 DeepSeek V3 完成