← 返回题目列表

AtCoder · abc343_d

G. 分数的多样性

中文机器翻译题面 查看原题

分数: 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