分数: 300 点
问题陈述
有 N 单元格从左到右排列成一行。 最初,任何单元格中都没有放置任何块。
你被给予 Q 查询,因此请按顺序处理。 每个查询都是以下两种类型之一:
1 x:地点 1 块中 x左侧第一个单元格。那么,如果每个细胞至少有 1 阻止、删除 1 阻止每个单元格。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
- 所有输入值均为整数。
- 至少存在一个第二类型的查询。
输入
输入由标准输入按以下格式给出:
N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
每个查询 \mathrm{query}_i (1 \leq i \leq Q) 采用以下格式之一给出:
1 x
2 y
输出
让 K 是第二类查询的数量。输出 K 行。的 i第行 (1 \leq i \leq K) 应包含以下问题的答案 i第二类型的第一个查询。
示例输入 1
3 7 1 1 1 3 1 3 2 1 2 2 1 2 2 1
示例输出 1
2 1 1
N=3,以及最初放置在 1-st, 2-nd, 3- 从左边开始的第一个单元格是 (0, 0, 0)。 查询按如下顺序处理:
- 地点 1 块中 1- 左边第一个单元格。存在没有块的单元格,因此不采取进一步的操作。中的块数 1-st, 2-nd, 3-rd 细胞变成 (1, 0, 0).
- 地点 1 块中 3- 从左边起第一个单元格。中的块数 1-st, 2-nd, 3-rd 细胞变成 (1, 0, 1).
- 地点 1 块中 3- 从左边起第一个单元格。中的块数 1-st, 2-nd, 3-rd 细胞变成 (1, 0, 2).
- 至少具有 1 块是 1-st 和 3- 从左边开始第一个单元格,所以有 2 这样的细胞。因此,输出 2.
- 至少具有 2 块只是 3- 从左边开始第一个单元格,所以有 1 这样的细胞。因此,输出 1.
- 地点 1 块中 2- 从左边数第一个单元格。此时,每个细胞至少有 1 块,所以 1 块已从每个单元格中删除。中的块数 1-st, 2-nd, 3-rd 细胞变成 (0, 0, 1).
- 至少具有 1 块只是 3- 从左边开始第一个单元格,所以有 1 这样的细胞。因此,输出 1.
因此,输出 2, 1, 1 按此顺序,每行一个。