D - 切割木材

得分：400分

问题描述

我们有一段长度为$L$米的木头。
对于每个$x = 1,2,\dots, L-1$，在距离木材左端$x$米的位置上有一个叫做标记$x$的标记。

给定$Q$个查询，第$i$个查询表示为一对数字$(c_i, x_i)$。
按照如下顺序处理查询：

• 如果 $c_i = 1$：在标记$x_i$处将木材切成两块。
• 如果 $c_i = 2$：选择带有标记$x_i$的木块并打印其长度。

这里，对于$c_i = 1$和$c_i = 2$的查询，确保在处理查询时标记$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$个这样的查询的回答。

5 3
2 2
1 3
2 2

5
3

在第一个查询时，没有进行切割，所以带有标记$2$的木块的长度为$5$米。因此，您应该打印$5$。
在第二个查询时，木块被切成两块，长度分别为$3$米和$2$米。
在第三个查询时，带有标记$2$的木块的长度为$3$米，因此您应该打印$3$。

5 3
1 2
1 4
2 3

2

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

69
31
6
38
38