实时积分多样性统计问题hard版

与$easy$版的区别在于$B_i$的数据范围，涉及到另一种数据结构的选择

题目描述

有 $N$ 名参赛选手（编号 $1$ 到 $N$），初始积分均为 $0$ 分。比赛过程中将发生 $T$ 次得分变化：

• 在 $i$ 秒时（$1 \leq i \leq T$），选手 $A_i$ 的积分增加 $B_i$ 分
• 每个得分变化事件相互独立且不会重复

要求计算每个时刻后的积分多样性：

• 对于每个 $i=1,2,...,T$，求出在 $i+0.5$ 秒时所有选手积分中不同数值的个数
  （例如：若积分为 $[10,20,30,20]$，则不同数值个数为 $3$）

输入格式

输入按照下方格式:

$N$ $T$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_T$ $B_T$

数据范围保证满足以下范围：

• $1\leq N, T\leq 2\times 10^5$
• $1\leq A_i \leq N$
• $1\leq B_i \leq 10^9$
• 所有输入的数据都是整数.

输出格式

输出一共$T$行，第$i$行的答案表示在第$i+0.5$秒时，一共有多少种不同的分数

样例

3 4
1 10
3 20
2 10
2 10

2
3
2
2

选手积分变化示例1详解

初始状态

设三位选手的积分序列为 $S = [S_1, S_2, S_3]$，初始状态为：

操作过程与结果

第1次操作（1秒时）

• ​操作：选手1 增加10分
• ​更新后积分：$$S = \{10, 0, 0\}$$
• ​在1.5秒时统计：

  不同积分值为 10 和 0 → ​2种不同值

第2次操作（2秒时）

• ​操作：选手3 增加20分
• ​更新后积分：$$S = \{10, 0, 20\}$$
• ​在2.5秒时统计：

  不同积分值为 10、0、20 → ​3种不同值

第3次操作（3秒时）

• ​操作：选手2 增加10分
• ​更新后积分：$$S = \{10, 10, 20\}$$
• ​在3.5秒时统计：

  不同积分值为 10 和 20 → ​2种不同值

第4次操作（4秒时）

• ​操作：选手2 再增加10分
• ​更新后积分：$$S = \{10, 20, 20\}$$
• ​在4.5秒时统计：

  不同积分值为 10 和 20 → ​2种不同值

最终统计结果

1 3
1 3
1 4
1 3

1
1
1

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

2
2
3
3
4
4
5
5
6
5