AT_acl1_d.Keep Distances

数轴上有 $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$ 的大小在满足上述条件的集合中最大。

对于每个查询，求所有好集合的并集的大小。

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

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

对于每个查询，输出所有好集合的并集的大小，每行一个结果。

限制条件

• $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$
• 输入均为整数。

样例解释 1

对于第 $1$ 个查询，最多可以选择 $3$ 个点组成集合。好集合有 $\{1,4,7\}$ 和 $\{1,4,8\}$ 这两种。因此，所有好集合的并集大小为 $|\{1,4,7,8\}|=4$。对于第 $2$ 个查询，最多只能选择 $1$ 个点组成集合。好集合有 $\{1\}$ 和 $\{2\}$ 这两种。因此，所有好集合的并集大小为 $|\{1,2\}|=2$。

由 ChatGPT 4.1 翻译