分数: 400 点
问题陈述
高桥正在举办一场比赛 N 玩家编号 1 to N。 选手们将争夺积分。目前,所有球员积分为零。
高桥的预知能力让他知道选手的成绩会如何变化。具体来说,对于 i=1,2,\dots,T, 玩家得分 A_i 将增加 B_i 指向 i 秒后。分数不会有其他变化。
高桥喜欢分数的多样性,他想知道每个时刻玩家的分数中会出现多少个不同的分数值。对于每个 i=1,2,\dots,T,找出玩家得分中不同得分值的个数 i+0.5 几秒钟后。
例如,如果玩家有 10, 20, 30,和 20 某一时刻,玩家的分数中有3个不同的分数值。
约束
- 1\leq N, T\leq 2\times 10^5
- 1\leq A_i \leq N
- 1\leq B_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
让 S 是玩家分数的序列 1, 2, 3 按此顺序。 目前, S=\lbrace 0,0,0\rbrace.
- 一秒后,玩家的得分 1 增加 10 点,制作 S=\lbrace 10,0,0\rbrace。因此,玩家的分数中有两个不同的分数值 1.5 几秒钟后。
- 两秒后,玩家的得分 3 增加 20 点,制作 S=\lbrace 10,0,20\rbrace。因此,玩家的分数中存在三个不同的分数值 2.5 几秒钟后。
- 三秒后,玩家的得分 2 增加 10 点,制作 S=\lbrace 10,10,20\rbrace。因此,玩家的分数中有两个不同的分数值 3.5 几秒钟后。
- 四秒后,玩家的得分 2 增加 10 点,制作 S=\lbrace 10,20,20\rbrace。因此,玩家的分数中有两个不同的分数值 4.5 几秒钟后。
示例输入 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