AT_abc343_d [ABC343D] Diversity of Scores

题目描述

有 $N$ 名编号为 $1$ 到 $N$ 的选手参加了高桥君主办的比赛。比赛中每位选手的得分初始均为 $0$。

高桥君拥有预知未来的能力，他已经知道接下来选手们的得分变化。具体来说，对于 $i=1,2,\dots,T$，在现在起第 $i$ 秒后，第 $A_i$ 号选手的得分会增加 $B_i$ 分。除此之外，得分不会有其他变化。

高桥君喜欢得分的多样性，他想知道每一时刻选手们的得分中有多少种不同的值。请你对于每个 $i=1,2,\dots,T$，求出在现在起第 $i+0.5$ 秒后，选手们的得分中有多少种不同的值。

例如，某一时刻选手们的得分分别为 $10,20,30,20$，那么此时得分中有 $3$ 种不同的值。

输入格式

输入按以下格式从标准输入读入。

$N$ $T$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_T$ $B_T$

输出格式

输出 $T$ 行。对于每个 $i\ (1\leq i \leq T)$，第 $i$ 行输出在现在起第 $i+0.5$ 秒后选手们的得分中有多少种不同的值。

输入输出样例 #1

输入 #1

3 4
1 10
3 20
2 10
2 10

输出 #1

2
3
2
2

输入输出样例 #2

输入 #2

1 3
1 3
1 4
1 3

输出 #2

1
1
1

输入输出样例 #3

输入 #3

10 10
7 2620
9 2620
8 3375
1 3375
6 1395
5 1395
6 2923
10 3375
9 5929
5 1225

输出 #3

2
2
3
3
4
4
5
5
6
5

说明/提示

约束条件

• $1\leq N,\ T\leq 2\times 10^5$
• $1\leq A_i \leq N$
• $1\leq B_i \leq 10^9$
• 输入均为整数

样例解释 1

将选手 $1,2,3$ 的得分按顺序组成数列 $S$。初始时，$S=\lbrace 0,0,0\rbrace$。

• 1 秒后，第 1 号选手得分增加 10，$S=\lbrace 10,0,0\rbrace$。因此，1.5 秒后得分有 $2$ 种不同的值。
• 2 秒后，第 3 号选手得分增加 20，$S=\lbrace 10,0,20\rbrace$。因此，2.5 秒后得分有 $3$ 种不同的值。
• 3 秒后，第 2 号选手得分增加 10，$S=\lbrace 10,10,20\rbrace$。因此，3.5 秒后得分有 $2$ 种不同的值。
• 4 秒后，第 2 号选手得分增加 10，$S=\lbrace 10,20,20\rbrace$。因此，4.5 秒后得分有 $2$ 种不同的值。

由 ChatGPT 4.1 翻译