AT_abc435_e.[ABC435E] Cover query

有 $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$ 个格子中仍为白色的格子的数量。

输入通过标准输入提供，格式如下：

$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$ 个格子从左到右排成一排。

• 第一次操作将第 $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$，一行一个。

数据范围

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

由 ChatGPT 5 翻译