镜与谜烟的彼方
Description
在和西风骑士团火花骑士交流之后，Naganohara Yoimiya 尝试制作了 n 个炸弹，编号分别为 1,2,⋯,n；她计划将编号为 i 的炸弹埋在数轴上的 ai 位置。
每个炸弹的爆炸范围都是一个确定的正整数 d，如果引爆一个位置 p 的炸弹，那么位置在 [p−d,p+d] 内的炸弹都会被引爆；这些被引爆的炸弹也可能进一步引爆更多的炸弹。
Naganohara Yoimiya 认为一个炸弹区间 [l,r] 是好的，当且仅当：如果她现在埋下编号在区间 [l,r] 内的炸弹（其中编号为 i 的炸弹被埋放在位置 ai），那么任意选择埋下的炸弹中的某一个引爆，都会导致埋下的所有炸弹被引爆。
现在给出 Naganohara Yoimiya 计划埋下炸弹的位置 a1,a2,⋯,an，以及炸弹的爆炸范围 d，Yoimiya 会进行 q 次询问，每次询问会给出区间 [L,R]，问有多少子区间 L≤l≤r≤R 是一个好的炸弹区间。
Input Format
第一行三个正整数 n,d,q。
第二行 n 个正整数 a1,a2,⋯,an。
接下来 q 行，每行两个正整数 L,R 表示一组询问。
Output Format
对于每组询问，输出一行一个非负整数表示答案。7 3 2
3 7 1 6 3 11 9
1 4
3 75
10Hint
数据范围
对于所有数据，1≤n,q≤3×105,1≤ai,d≤109。
| 测试点编号 | n≤ | q≤ | 特殊性质 |
|---|---|---|---|
| 1,2 | 10 | 10 | 无 |
| 3 | 2000 | 2000 | 无 |
| 4,5 | 2000 | 2×105 | 无 |
| 6,7,8 | 2×105 | 2×105 | ai≤ai+1 |
| 9,10,11 | 2×105 | 1 | 询问满足 L=1,R=n |
| 12,13,14,15 | 2×105 | 2×105 | 询问满足 L=1 |
| 16,17 | 105 | 105 | 数据随机生成 |
| 18,19,20 | 105 | 105 | 无 |
| 21,22 | 2×105 | 2×105 | 无 |
| 23,24,25 | 3×105 | 3×105 | 无 |
其中数据随机生成的方式为：首先确定 n=105,q=105，然后在 [1,109] 范围内随机生成 d 和每个 ai，然后随机生成 q 个区间 [L,R]，每个区间都在所有区间中等概率选取。
样例解释
所有好的炸弹区间为：[1,1],[1,4],[1,5],[1,7],[2,2],[2,5],[2,7],[3,3],[3,5],[3,7],[4,4],[4,5],[4,7],[5,5],[6,6],[6,7],[7,7]
附件
Source
NOIP模拟题 2024相关
在下列比赛中: