一个范围内的已连接城市数量

在阵列A中有N个城市.还有一辆自行车可以在城市之间的最多K个单位旅行.

我们需要回答Q问题.每个查询都具有LR X形式.它询问可从城市X到达的城市数量,这些城市在A中的L和R之间(1 - 索引).每个城市都有一个汽油泵,因此您可以假设燃料在到达时会得到补充.

例:

A = [4,3,1,9,6],K = 2

Q1 = 1 3 6 =>(3)

Q2 = 1 5 3 =>(4)

在Q1,从6号城市出发,您可以前往4号城市,然后前往3号城市,然后前往1号城市.

在第二季度,从3号城市出发,您可以前往9号城市以外的所有城市.

约束:

N <= 10 ^ 5且Q <= 10 ^ 5且K <= 10 ^ 8

我该如何解决这个问题？显然,不可能从每个X执行DFS/BFS,因为它非常昂贵并且会超时.我试着想到Disjoint集合加入彼此距离K的城市,但我对它没有一个非常明确的想法.

任何帮助表示赞赏.谢谢!