E - E-liter 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

N 行 N 列のグリッドがあります。はじめ、すべてのマスは白く塗られています。

Q 回のクエリを与えられる順に処理してください。各クエリは以下のいずれかです。

  • タイプ 1: 整数 R が与えられる。グリッドの上から R 行目のマスをすべて黒く塗る。
  • タイプ 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

より大きなケースでのオーバーフローに注意してください。

Score : 475 points

Problem Statement

There is an N \times N grid. Initially, all cells are painted white.

Process Q queries in the given order. Each query is one of the following:

  • Type 1: An integer R is given. Paint all cells in the R-th row from the top of the grid black.
  • Type 2: An integer C is given. Paint all cells in the C-th column from the left of the grid white.

After processing each query, output the number of black cells in the grid at that point.

Constraints

  • 1 \leq N, Q \leq 3 \times 10^5
  • For type 1 queries, 1 \leq R \leq N.
  • For type 2 queries, 1 \leq C \leq N.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, \text{query}_i is the i-th query, given in one of the following formats.

Type 1:

1 R

Type 2:

2 C

Output

Output Q lines. The i-th line should contain the number of black cells in the grid at the time the i-th query has been processed.

Sample Input 1

3 4
1 1
1 3
2 2
1 1

Sample Output 1

3
6
4
5

The changes in the grid are shown using characters. . represents a white cell, and # represents a black cell.

...    ###    ###    #.#    ###
... -> ... -> ... -> ... -> ...
...    ...    ###    #.#    #.#

Sample Input 2

300000 1
2 300000

Sample Output 2

0

Beware of overflow in larger cases.