← 返回题目列表

AtCoder · acl1_d

D. 保持距离

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

分数: 800 点

问题陈述

有 N 点在数轴上, i- 第一个放置在坐标上 X_i。 这些点按坐标递增顺序编号。 换句话说,对于所有 i (1 \leq i \leq N-1), X_i < X_{i+1} 成立。 除此之外,还有一个整数 给出了 K 。

流程 Q 查询。

在 i第一个查询,两个整数 给出了 L_i 和 R_i 。 这里,一组 s 的积分据说是 好 如果满足以下所有条件则设置。 请注意,好集合的定义因查询而异。

  • 中的每个点 s 是其中之一 X_{L_i},X_{L_i+1},\ldots,X_{R_i}.
  • 对于任意两个不同的点 s,它们之间的距离大于或等于 K.
  • 的大小 s 是满足上述条件的所有集合中的最大值。

对于每个查询,找到所有好集合的并集大小。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 0 \leq X_1 < X_2 < \cdots < X_N \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq L_i \leq R_i \leq N
  • 输入中的所有值都是整数。

输入

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

N K
X_1 X_2 \cdots X_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

输出

对于每个查询,打印一行中所有好集合的并集大小。


示例输入 1

5 3
1 2 4 7 8
2
1 5
1 2

示例输出 1

4
2

在第一个查询中,最多可以有 3 点很好。 存在两个好的集合: \{1,4,7\} 和 \{1,4,8\}。 因此,所有好集合的并集大小为 |\{1,4,7,8\}|=4.

在第二个查询中,最多可以有 1 点设置好。 存在两个好的集合: \{1\} 和 \{2\}。 因此,所有好集合的并集大小为 |\{1,2\}|=2.


示例输入 2

15 220492538
4452279 12864090 23146757 31318558 133073771 141315707 263239555 350278176 401243954 418305779 450172439 560311491 625900495 626194585 891960194
5
6 14
1 8
1 13
7 12
4 12

示例输出 2

4
6
11
2
3