4215: Diversity of Scores

# Diversity of Scores ### 内存 1024MB ### 时间 2S ## 题目描述 小高正在举办一场有 $N$ 名选手参加的比赛。选手编号从 $1$ 到 $N$。选手们将争夺积分。目前，所有选手的积分都是零。小高的预知能力让他知道选手们的分数将如何变化。具体来说，对于 $i=1,2,\dots,T$，第 $A_i$ 号选手的分数将在 $i$ 秒后增加 $B_i$ 分。除此之外，分数不会有其他变化。小高喜欢分数的多样性，他想知道在每个时刻选手们的分数中有多少种不同的值。对于每个 $i=1,2,\dots,T$，请找出在 $i+0.5$ 秒后选手们的分数中有多少种不同的值。例如，如果在某个时刻选手们的分数是 $10$、$20$、$30$ 和 $20$，那么在那个时刻选手们的分数中有三种不同的值。 ## 输入格式 输入按以下格式从标准输入给出： $N$ $T$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_T$ $B_T$ ## 输出格式 输出 $T$ 行。第 $i$ 行 $(1 \leq i \leq T)$ 应包含一个整数，表示在 $i+0.5$ 秒后选手们的分数中有多少种不同的值。 ## 输入输出样例 ### 输入样例1 ``` 3 4 1 10 3 20 2 10 2 10 ``` ### 输出样例1 ``` 2 3 2 2 ``` ### 输入样例2 ``` 1 3 1 3 1 4 1 3 ``` ### 输出样例2 ``` 1 1 1 ``` ### 输入样例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说明】 让 $S$ 表示选手 $1$、$2$、$3$ 的分数序列。目前，$S=\{0,0,0\}$。 - 一秒后，选手 $1$ 的分数增加 $10$ 分，使得 $S=\{10,0,0\}$。因此，在 $1.5$ 秒后选手们的分数中有两种不同的值。 - 两秒后，选手 $3$ 的分数增加 $20$ 分，使得 $S=\{10,0,20\}$。因此，在 $2.5$ 秒后选手们的分数中有三种不同的值。 - 三秒后，选手 $2$ 的分数增加 $10$ 分，使得 $S=\{10,10,20\}$。因此，在 $3.5$ 秒后选手们的分数中有两种不同的值。 - 四秒后，选手 $2$ 的分数增加 $10$ 分，使得 $S=\{10,20,20\}$。因此，在 $4.5$ 秒后选手们的分数中有两种不同的值。 【数据范围】 $1 \leq N, T \leq 2 \times 10^5$ $1 \leq A_i \leq N, 1 \leq B_i \leq 10^9$ 所有输入值都是整数。 ## 题目来源 ABC343D