← 返回题目列表

AtCoder · abc435_e

H. 封面查询

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

分数: 450 点

问题陈述

有 N 单元格从左到右排列成一行。
的 i左侧第一个单元格 (1\leq i\leq N) 称为单元格 i.
最初,所有单元格都漆成白色。

流程 Q 按顺序查询。
的 i第一个查询 (1\leq i\leq Q) 如下:

两个整数 给出了 (L_i,R_i) (1\leq L_i\leq R_i\leq N) 。
绘制所有单元格 L_i, L_i+1, \ldots, R_i 黑色。
在这里,涂成白色的单元格现在涂成黑色,涂成黑色的单元格保持原样。
之后,找到单元格的数量(其中 已绘制的 N 单元格) 白色.

约束

  • 1\leq N\leq 10^9
  • 1\leq Q\leq 2\times 10^5
  • 1\leq L_i\leq R_i\leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

输出

输出 Q 行。
的 i第行 (1\leq i\leq Q) 应包含以下问题的答案 i第一个查询。


示例输入 1

10 5
3 5
8 9
5 8
2 9
6 6

示例输出 1

7
5
3
2
2

最初, 10 单元格从左到右排列成一行。

  • 第一个查询绘制单元格 3,4,5 黑色。手术后,涂成白色的细胞就是细胞 1,2,6,7,8,9,10,即 7 细胞。
  • 第二个查询绘制单元格 8,9 黑色。手术后,涂成白色的细胞是 1,2,6,7,10,即 5 细胞。
  • 第三个查询绘制单元格 5,6,7,8 黑色。手术后,涂成白色的细胞是 1,2,10,即 3 细胞。
  • 第四个查询绘制单元格 2,3,\ldots,9 黑色。手术后,涂成白色的细胞是 1,10,即 2 细胞。
  • 第五个查询绘制单元格 6 黑色。手术后,涂成白色的细胞就是细胞 1,10,即 2 细胞。

因此,输出 每行按此顺序 7,5,3,2,2 。


示例输入 2

1000000000 1
1 500000000

示例输出 2

500000000