C - Drop Blocks

题目描述

有 (N) 个格子从左到右排成一行。初始时，每个格子中都没有方块。

给定 (Q) 个询问，请按顺序处理。每个询问属于以下两种类型之一：

类型 1

1 x

在从左往右数第 (x) 个格子中放入 (1) 个方块。

然后，如果此时每个格子中都至少有 (1) 个方块，则从每个格子中都移除 (1) 个方块。

类型 2

2 y

输出当前至少有 (y) 个方块的格子数量。

约束条件

• (1 \leq N \leq 3 \times 10^5)
• (1 \leq Q \leq 3 \times 10^5)
• (1 \leq x \leq N)
• (1 \leq y \leq 3 \times 10^5)
• 所有输入值均为整数。
• 至少存在一个类型 2 的询问。

输入格式

输入从标准输入给出，格式如下：

N Q
query_1
query_2
...
query_Q

其中，第 (i) 个询问 (query_i) ((1 \leq i \leq Q)) 的格式为以下两种之一：

1 x

或

2 y

输出格式

设类型 2 的询问共有 (K) 个。

请输出 (K) 行。第 (i) 行 ((1 \leq i \leq K)) 应输出第 (i) 个类型 2 询问的答案。

样例 1

输入

3 7
1 1
1 3
1 3
2 1
2 2
1 2
2 1

输出

2
1
1

样例解释

(N = 3)，初始时，从左往右第 (1)、第 (2)、第 (3) 个格子中的方块数量为：

(0, 0, 0)

按顺序处理询问如下：

1. 在第 (1) 个格子中放入 (1) 个方块。 此时仍然存在没有方块的格子，因此不进行额外操作。 各格子的方块数量变为：

   (1, 0, 0)
   

2. 在第 (3) 个格子中放入 (1) 个方块。 各格子的方块数量变为：

   (1, 0, 1)
   

3. 在第 (3) 个格子中放入 (1) 个方块。 各格子的方块数量变为：

   (1, 0, 2)
   

4. 至少有 (1) 个方块的格子是第 (1) 个和第 (3) 个，共有 (2) 个。 因此输出：

   2
   

5. 至少有 (2) 个方块的格子只有第 (3) 个，共有 (1) 个。 因此输出：

   1
   

6. 在第 (2) 个格子中放入 (1) 个方块。 此时每个格子都至少有 (1) 个方块，因此从每个格子中都移除 (1) 个方块。 各格子的方块数量变为：

   (0, 0, 1)
   

7. 至少有 (1) 个方块的格子只有第 (3) 个，共有 (1) 个。 因此输出：

   1
   

所以，最终按顺序输出：

2
1
1