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