分数: 300 点
问题陈述
有 N 某个操作系统的版本,编号 1,2,\dots,N 按时间顺序排列。
有 N PC,以及最初的操作系统版本 i第 PC 是 i.
执行 Q 操作按顺序进行。的 i第次操作如下:
- 升级当前操作系统版本为 X_i 或更早版本 Y_i(>X_i)。然后,打印本次操作升级的PC数量。
请注意,对于 i<Q,从 i在继续之前执行第一个操作 (i+1)第次操作。
约束
- 所有输入值均为整数。
- 2 \le N \le 10^6
- 1 \le Q \le 2 \times 10^5
- 1 \le X_i < Y_i \le N
输入
输入由标准输入按以下格式给出:
N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
输出
输出 Q 行。
的 i- 第行应包含升级的 PC 数量 i第次操作。
示例输入 1
8 5 2 6 3 5 1 7 5 7 7 8
示例输出 1
2 1 0 3 7
该输入包含五个操作。
- 最初,八台PC的版本是 1,2,3,4,5,6,7,8.
- 在第一次操作中,具有版本的电脑 2 或更早版本升级到 6.
- 该操作升级两台PC,PC版本变为 6,6,3,4,5,6,7,8.
- 在第二次操作中,具有版本的 PC 3 或更早版本升级到 5.
- 该操作升级一台PC,PC版本变为 6,6,5,4,5,6,7,8.
- 在第三次操作中,具有版本的 PC 1 或更早版本升级到 7.
- 该操作升级零台电脑,电脑版本变为 6,6,5,4,5,6,7,8.
- 在第四次操作中,具有版本的 PC 5 或更早版本升级到 7.
- 该操作升级三台PC,PC版本变为 6,6,7,7,7,6,7,8.
- 在第五次操作中,具有版本的 PC 7 或更早版本升级到 8.
- 该操作升级7台PC,PC版本变为 8,8,8,8,8,8,8,8.