Количество связанных городов в диапазоне

Question

В массиве A дано N городов. Есть также велосипед, который может проехать не более K единиц между городами.

Есть Q вопросов, на которые мы должны ответить.Каждый запрос имеет форму LR X. Он запрашивает количество городов, доступных из города X, которые находятся между L и R в A (1 - проиндексирован).В каждом городе есть бензонасос, поэтому вы можете предполагать, что топливо будет пополняться по мере его поступления.

Пример:

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

Q1 = 1 3 6 => (3)

Q2 = 1 5 3 => (4)

В Q1 из города 6 вы можете перейти в город 4, затем в город 3, а затем в 1.

Во 2-м квартале из города 3 вы можете перейти во все города, кроме города, на 9.

Ограничения:

N <= 10 ^ 5 и Q <= 10 ^ 5 и K <= 10 ^ 8 </p>

Как мне решить эту проблему?Очевидно, что невозможно сделать DFS / BFS из каждого X, потому что это очень дорого и истечет время ожидания.Я пытался придумать наборы 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).