← 返回题目列表

AtCoder · abc217_d

G. 砍伐木材

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

分数: 400 点

问题陈述

我们有一块长木头,长度为 L 米。
对于每个 x = 1, 2, \dots, L - 1,有一个标记叫Mark x at x 距离作品左端米。

你被给予 Q 查询, i- 第一个表示为一对数字 (c_i, x_i).
按升序处理查询 i 如下所述。

  • If c_i = 1:在标记处剪下一块 x_i 一分为二。
  • If c_i = 2:选择带有标记的作品 x_i 并打印其长度。

这里,对于两种查询 c_i = 1, 2,保证Mark处不会被剪切 x_i 当要处理查询时。

约束

  • 1 \leq L \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • c_i = 1, 2 (1 \leq i \leq Q)
  • 1 \leq x_i \leq L - 1 (1 \leq i \leq Q)
  • 对于每个 i (1 \leq i \leq Q),以下成立:不存在 j 这样 1 \leq j \lt i 和 (c_j,x_j) = (1, x_i).
  • 输入中的所有值都是整数。

输入

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

L Q
c_1 x_1
c_2 x_2
\vdots
c_Q x_Q

输出

打印行数等于查询数 c_i = 2。 在 j第行,打印对 j-第一个这样的查询。


示例输入 1

5 3
2 2
1 3
2 2

示例输出 1

5
3

第一次查询时,还没有进行过切割,所以带有Mark的那一块 2 的长度为 5 米。因此,您应该打印 5.
在第二个查询中,该块被切成两块,长度为 3 和 2 米。
第三次查询时,带有Mark的那篇文章 2 的长度为 3 米,所以你应该打印 3.


示例输入 2

5 3
1 2
1 4
2 3

示例输出 2

2

示例输入 3

100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

示例输出 3

69
31
6
38
38