AtCoder Beginner Contest 466
放置车AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There is a grid with $N$ rows and $N$ columns.
有一个网格，它有 $N$ 行 $N$ 列。AI (CI翻译)
Initially, nothing is placed on the grid.
Starting from this state, Takahashi performs $M$ operations on the grid in order. The $i$-th operation $(1\leq i\leq M)$ is as follows.
初始时，网格上没有放置任何棋子。
从这个状态开始，高桥依次对网格进行 $M$ 次操作。第 $i$ 次操作 $(1\leq i\leq M)$ 如下：AI (CI翻译)
- Remove all pieces placed on the cells in the
$R_i$-th row from the top. - Next, remove all pieces placed on the cells in the
$C_i$-th column from the left. - Finally, place a piece on the cell at the
$R_i$-th row from the top and the$C_i$-th column from the left.
- 移除位于从上往下第
$R_i$行各个格子上的所有棋子。 - 接着，移除位于从左往右第
$C_i$列各个格子上的所有棋子。 - 最后，在从上往下第
$R_i$行、从左往右第$C_i$列的格子上放置一个棋子。
Output the number of pieces placed on the grid after the $M$ operations.
输出进行 $M$ 次操作后网格上棋子的数量。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \leq N \leq 3\times 10^5$$1 \leq M \leq 3\times 10^5$$1 \leq R_i \leq N$$1 \leq C_i \leq N$- All input values are integers.
$1 \leq N \leq 3\times 10^5$$1 \leq M \leq 3\times 10^5$$1 \leq R_i \leq N$$1 \leq C_i \leq N$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N M
R_1 C_1
R_2 C_2
\vdots
R_M C_MN M
R_1 C_1
R_2 C_2
\vdots
R_M C_MOutput
输出格式
AI (CI翻译)Output the number of pieces placed on the grid after the $M$ operations.
输出进行 $M$ 次操作后网格上棋子的数量。AI (CI翻译)
样例
Input #1
3 6
1 1
1 2
3 3
3 2
1 3
1 3
Output #1
2
Initially, nothing is placed on the grid with three rows and three columns, and pieces are removed and placed by each operation as follows.
Below, the cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i,j)$.
- In the first operation, a piece is placed on cell $(1,1)$.
- In the second operation, the piece is removed from cell $(1,1)$, and a piece is placed on cell $(1,2)$.
- In the third operation, a piece is placed on cell $(3,3)$.
- In the fourth operation, the pieces are removed from cell $(1,2)$ and cell $(3,3)$, and a piece is placed on cell $(3,2)$.
- In the fifth operation, a piece is placed on cell $(1,3)$.
- In the sixth operation, the piece is removed from cell $(1,3)$, and a piece is placed on cell $(1,3)$ again.
In the final state, there is one piece each on cell $(1,3)$ and cell $(3,2)$, so output $2$.
Input #2
2 3
1 2
2 1
1 1
Output #2
1
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。