1351: [蓝桥杯 2024 省 C] 商品库存管理

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:12 Solved:5

Description

在库存管理系统中,跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品,这些商品根据类别和规格被有序地分类并编号,编号范围从 1 至 n。初始时,每种商品的库存量均为 0

为了高效地监控和调整库存量,小蓝的管理团队设计了 m 个操作,每个操作涉及到一个特定的商品区间,即一段连续的商品编号范围(例如区间 [L,R])。执行这些操作时,区间内每种商品的库存量都将增加 1。然而,在某些情况下,管理团队可能会决定不执行某些操作,使得这些操作涉及的商品区间内的库存量不会发生改变,维持原有的状态。

现在,管理团队需要一个评估机制,来确定如果某个操作未被执行,那么最终会有多少种商品的库存量为 0。对此,请你为管理团队计算出,对于每个操作,如果不执行该操作而执行其它操作,库存量为 0 的商品的种类数。

Input

输入的第一行包含两个整数 n 和 m,分别表示商品的种类数和操作的个数。

接下来的 m 行,每行包含两个整数 L 和 R,表示一个操作涉及的商品区间。

Output

输出 m 行,每行一个整数,第 i 行的整数表示如果不执行第 i 个操作,则最终库存量为 0 的商品种类数

Sample Input Copy

5 3
1 2
2 4
3 5

Sample Output Copy

1
0
1

HINT

【样例说明】

考虑不执行每个操作时,其余操作对商品库存的综合影响:

  • 不执行操作 1:剩余的操作是操作 2(影响区间 [2,4])和操作 3(影响区间 [3,5])。执行这两个操作后,商品库存序列变为 [0,1,2,2,1]。在这种情况下,只有编号为 1 的商品的库存量为 0。因此,库存量为 0 的商品种类数为 1

  • 不执行操作 2:剩余的操作是操作 1(影响区间 [1,2])和操作 3(影响区间 [3,5])。执行这两个操作后,商品库存序列变为 [1,1,1,1,1]。在这种情况下,所有商品的库存量都不为 0。因此,库存量为 0 的商品种类数为 0

  • 不执行操作 3:剩余的操作是操作 1(影响区间 [1,2])和操作 2(影响区间 [2,4])。执行这两个操作后,商品库存序列变为 [1,2,1,1,0]。在这种情况下,只有编号为 5 的商品的库存量为 0。因此,库存量为 0 的商品种类数为 1

【评测用例规模与约定】

对于 20% 的评测用例,1n,m5×1031LRn
对于所有评测用例,1n,m3×1051LRn