← 返回题目列表

AtCoder · past202109_j

J. 反转数组

中文机器翻译题面 查看原题

分数: 6 点

警告

2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

我们有一个长度为 2N: A = (1,2, \ldots ,2N)。工艺流程 Q 查询。在 i-th 查询,您得到整数 t_i 和 k_i.

  • If t_i = 1:打印的值 k_i- 序列的第一个元素 A 从左边开始。
  • If t_i = 2:颠倒顺序 2k_i 元素位于序列的中心 A。换句话说,颠倒顺序 (N-k_i+1)-th 通过 (N+k_i)从左边算起第一个元素。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq t_i \leq 2
  • 至少有一个索引 i 这样 t_i=1.
  • 1 \leq k_i \leq 2N if t_i=1.
  • 1 \leq k_i \leq N if t_i=2.
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N Q
t_1 k_1
t_2 k_2
\vdots
t_Q k_Q

输出

对于每个 i 这样 t_i=1,打印的值 k_i- 序列的第一个元素 A 从左边开始,独占一行。


示例输入 1

3 2
2 2
1 4

示例输出 1

3

最初,序列 A is (1,2,3,4,5,6).

在第一个查询中,我们反转中间的四个元素,使得 A = (1,5,4,3,2,6).

在第二个查询中,左起第四个元素是 3,所以你应该打印 3.


示例输入 2

3 3
2 3
1 3
1 1

示例输出 2

4
6

示例输入 3

5 6
2 2
2 1
2 1
2 3
1 2
2 3

示例输出 3

2