← 返回题目列表

AtCoder · abc461_e

E. E升

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

分数: 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

当心较大情况下的溢出。