分数: 475 点
问题陈述
有一个 N \times N 网格。最初,所有单元都被漆成白色。
流程 Q 按给定顺序查询。每个查询都是以下之一:
- 类型 1:整数 给出了 R 。绘制所有单元格 R- 从网格顶部算起的第 3 行黑色。
- 类型 2:整数 给出了 C 。绘制所有单元格 C- 网格左侧的第列白色。
处理每个查询后,输出该点网格中黑色单元格的数量。
约束
- 1 \leq N, Q \leq 3 \times 10^5
- 对于类型 1 查询, 1 \leq R \leq N.
- 对于类型 2 查询, 1 \leq C \leq N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, \text{query}_i 是 i-第一个查询,以下列格式之一给出。
类型 1:
1 R
类型 2:
2 C
输出
输出 Q 行。的 i- 第行应包含当时网格中黑色单元格的数量 i第一个查询已处理。
示例输入 1
3 4 1 1 1 3 2 2 1 1
示例输出 1
3 6 4 5
网格中的变化用字符显示。 . 代表一个白细胞,并且 # 代表黑色单元格。
... ### ### #.# ### ... -> ... -> ... -> ... -> ... ... ... ### #.# #.#
示例输入 2
300000 1 2 300000
示例输出 2
0
当心较大情况下的溢出。