一个范围内连接的城市数量
Number of connected cities in a range
数组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 and Q <= 10^5 and K <= 10^8
如何解决这个问题？显然不可能从每个 X 做一个 DFS / BFS，因为它非常昂贵并且会超时。我试着想过 Disjoint sets 加入彼此相距 K 距离以内的城市，但我对此不是很清楚。
感谢任何帮助。谢谢！
我推荐：
- 按位置对城市进行排序：[4, 3, 1, 9, 6] -> [1,3,4,6,9]
- 对此进行线性扫描可以让您确定哪些城市组可以相互到达。根据城市所在的组标记城市：[1,1,1,1,2]
- 根据起始城市的标签标记每个查询
- 将标签1的所有城市加入线段树
- 使用线段树回答所有标签 1 查询
- 从线段树中移除标签1城市
然后对每个标签重复步骤 4、5、6。
这应该给出 O(NlogN)+O(QlogN) 的总复杂度。
数组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 and Q <= 10^5 and K <= 10^8
如何解决这个问题？显然不可能从每个 X 做一个 DFS / BFS，因为它非常昂贵并且会超时。我试着想过 Disjoint sets 加入彼此相距 K 距离以内的城市，但我对此不是很清楚。
感谢任何帮助。谢谢！
我推荐：
- 按位置对城市进行排序：[4, 3, 1, 9, 6] -> [1,3,4,6,9]
- 对此进行线性扫描可以让您确定哪些城市组可以相互到达。根据城市所在的组标记城市：[1,1,1,1,2]
- 根据起始城市的标签标记每个查询
- 将标签1的所有城市加入线段树
- 使用线段树回答所有标签 1 查询
- 从线段树中移除标签1城市
然后对每个标签重复步骤 4、5、6。
这应该给出 O(NlogN)+O(QlogN) 的总复杂度。