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