And*_*ott 5 algorithm graph graph-algorithm
在阵列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的城市,但我对它没有一个非常明确的想法.
任何帮助表示赞赏.谢谢!
我建议：
然后对每个标签重复步骤 4、5、6。
这应该给出 O(NlogN)+O(QlogN) 的总复杂度。