[CEOI 2022] Abracadabra

Luogu

IDLGP8996

Time3000ms

Memory512MB

DifficultyP6

线段树平衡树树状数组2022CEOI（中欧）

Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。 Tin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 $n$ 张牌的顺序，接着采用如下技巧洗牌： 1. 拿起自顶向下 $\frac{n}{2}$ 张牌放在右手，自底向上 $\frac{n}{2}$ 张牌放在左手，牌的正面对着桌子。 1. 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。 1. 将还有牌的那只手上的所有牌放下。请你写一个程序模拟 Tin 的魔术。 ## Input 第一行两个整数 $N,Q$。接下来一行 $N$ 个整数 $p_i$，从底向上描述了整个牌堆。接下来 $Q$ 行，一行一个询问 $t,i$，表示询问 $t$ 次洗牌后自底向上第 $i$ 张牌编号是多少。 ## Output 对于每一个询问，输出你的答案。 [samples] ## Note ### 样例 3 解释 | 洗牌次数 | 自底向上的牌堆 | | :------: | :-----------------------------: | | $0$ | $7\ 5\ 2\ 9\ 10\ 8\ 4\ 3\ 6\ 1$ | | $1$ | $7\ 5\ 2\ 8\ 4\ 3\ 6\ 1\ 9\ 10$ | | $2$ | $3\ 6\ 1\ 7\ 5\ 2\ 8\ 4\ 9\ 10$ | | $3$ | $2\ 3\ 6\ 1\ 7\ 5\ 8\ 4\ 9\ 10$ | ### 数据规模与约定对于全部数据，满足 $1\le N\le 2\times 10^5$，$N$ 为偶数，$1\le Q\le 10^6$，$0\le t\le 10^9$，$p$ 为 $1\sim n$ 的排列，$1\le i\le N$。 | Subtask 编号 | 特殊限制 | 分数 | | :----------: | :------------------: | :------: | | $1$ | $N\le 10^3$ | $10$ | | $2$ | 每一个询问的 $t$ 相同 | $40$ | | $3$ | $N,Q\le 10^5$ | $25$ | | $4$ | 无特殊限制 | $25$ |

Samples

Input #1

6 3
1 5 6 2 3 4
1 2
0 4
1 5

Output #1

2
2
5

Input #2

6 6
2 1 5 4 6 3
0 1
1 1
0 3
1 3
0 6
10 6

Output #2

Input #3

10 10
7 5 2 9 10 8 4 3 6 1
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9
3 10

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2022] Abracadabra",
    "description": {
      "content": "Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。 Tin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。 事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8996"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。\n\nTin 会准备一套牌，总共 $n$ 张（保证 $n$ 为偶数），各编号为 $1\\sim n$，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 $t$ 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。\n\n事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments