Cutting Woods

题目描述

我们有一根长度为 $L$ 米的长木条。
对于每个 $x = 1, 2, \dots, L - 1$，在距木条左端 $x$ 米处有一个称为 Mark $x$ 的标记。 给出 $Q$ 个查询，第 $i$ 个查询以一对数字 $(c_i, x_i)$ 表示。
按 $i$ 的升序处理这些查询，具体如下。

如果 $c_i = 1$：在 Mark $x_i$ 处把木条切成两段。 如果 $c_i = 2$：选择包含 Mark $x_i$ 的那段木条并输出它的长度。

在这里，对于两类查询 $c_i = 1, 2$，保证在处理该查询时 Mark $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

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

提示

$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)$。 输入中的所有值都是整数。在第一次查询时尚未进行任何切割，所以包含 Mark $2$ 的那段长度为 $5$ 米。因此，你应该输出 $5$。
在第二次查询中，木条被切成两段，长度分别为 $3$ 米和 $2$ 米。
在第三次查询时，包含 Mark $2$ 的那段长度为 $3$ 米，所以你应该输出 $3$。

标签: AtCoder|abc217D

来源

AtCoder|abc217D