AT_abc230_d [ABC230D] Destroyer Takahashi

题目描述

在一个被划分为 $N$ 行 $10^9$ 列格子的城市中，有 $N$ 面墙，每面墙都被分配了从 $1$ 到 $N$ 的编号。
第 $i$ 面墙位于第 $i$ 行，从左起第 $L_i$ 列到第 $R_i$ 列的范围内。（也请参考输入输出样例 $1$ 的图示。）

高桥君决定要摧毁所有 $N$ 面墙。
拥有超人力量的高桥君可以用一次拳击同时对连续的 $D$ 列造成伤害。

• 更严格地说，可以选择一个 $1$ 到 $10^9 - D + 1$ 之间的整数 $x$，对第 $x$ 列到第 $x + D - 1$ 列范围内（只要有一部分在该范围内）的所有尚未被摧毁的墙造成拳击伤害。

只要墙的任意部分受到伤害，整面墙就会因拳击的冲击波而被彻底摧毁。
（也请参考输入输出样例 $1$ 的说明。）

请问高桥君至少需要多少次拳击才能摧毁所有的墙？

输入格式

输入以如下格式从标准输入读入。

$N$ $D$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

输出格式

输出摧毁所有墙所需的最少拳击次数。

输入输出样例 #1

输入 #1

3 3
1 2
4 7
5 9

输出 #1

2

输入输出样例 #2

输入 #2

3 3
1 2
4 7
4 9

输出 #2

1

输入输出样例 #3

输入 #3

5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

输出 #3

3

说明/提示

限制条件

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

样例解释 1

下图展示了与输入样例 $1$ 对应的墙的分布。

例如，可以如下方式进行拳击，仅用 $2$ 次拳击摧毁所有的墙。（下述说明中，$a$ 列到 $b$ 列的范围记作 $[a, b]$。）

• 首先，对 $[2, 4]$ 进行拳击。位于 $[2, 4]$ 的墙 $1$ 和墙 $2$ 受到伤害，被摧毁。
• 然后对 $[5, 7]$ 进行拳击。位于 $[5, 7]$ 的墙 $3$ 受到伤害，被摧毁。

另外，也可以如下方式用 $2$ 次拳击摧毁所有墙：

• 首先对 $[7, 9]$ 进行拳击，摧毁墙 $2$ 和墙 $3$。
• 然后对 $[1, 3]$ 进行拳击，摧毁墙 $1$。

样例解释 2

与输入输出样例 $1$ 相比，墙 $3$ 的范围从 $[5, 9]$ 变成了 $[4, 9]$。
在这种情况下，只需对 $[2, 4]$ 进行一次拳击即可摧毁所有的墙。

由 ChatGPT 4.1 翻译