← 返回题目列表

AtCoder · abc426_c

E. 需要升级

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

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