分数: 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