← 返回题目列表

AtCoder · abc459_c

C. 掉落方块

中文机器翻译题面 查看原题

分数: 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 按此顺序,每行一个。