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

Question

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

我们需要回答Q问题。每个查询的形式为L R 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的城市，但我对它没有一个非常明确的想法。

任何帮助表示赞赏。谢谢！

Answer 1

我建议：

1. 按城市位置排序城市：[4,3,1,9,6] - > [1,3,4,6,9]
2. 通过此线性扫描，您可以确定哪些城市可以相互访问。根据他们所在的群体标记城市：[1,1,1,1,2]
3. 根据其起始城市的标签标记每个查询
4. 将所有标签1城市添加到细分树中
5. 使用段树来回答所有标签1查询
6. 从段树中删除标签1个城市

然后对每个标签重复步骤4,5,6。

这应该给出O（NlogN）+ O（QlogN）的总复杂度。