Задача 175F - Gnomes of Might and Magic

Построим граф, вершины которого будут соответствовать замкам, а ребра — дорогам. Заметим, что степень каждой вершины в графе не превосходит 4, значит, количество ребер E <= 2 * N.

Для решения задачи научимся обрабатывать каждый запрос за время в среднем O(_log_(_N_)). Рассмотрим запрос на нахождение числа гномов, уничтоженных Миссией Смерти. Если принять за вес ребра количество гномов на соответствующей дороге, то нам необходимо найти кратчайший путь между двумя вершинами, а среди них — минимальный по числу ребер. Таким образом, путь характеризуется двумя числами — G и R — количество гномов и дорог (лексикографическую минимальность пока учитывать не будем). Одно ребро между вершинами u и v имеет характеристики (_C_(_u_,_v_), 1), где C(_u_,_v_) — количество гномов на ребре (_u_,_v_). Рассмотрим две вершины s и t, между которыми мы ищем путь. Кратчайший путь между ними может иметь один из двух видов:

• путь по Обходу Зла, если обе вершины находятся на одном Обходе
• путь вида s -> g1 -> g2 -> t, где g1 и g2 — вершины на Пути Добра, причем g1 и s лежат на одном Обходе, g2 и t лежат на одном обходе (некоторые из данных 4 вершин могут совпадать).

Значит, достаточно научиться быстро определять кратчайший путь между вершинами e1 и e2 по Обходу Зла и между вершинами g1 и g2 по Пути Добра. Для нахождения расстояния между вершинами по Обходу Зла заведем на ребрах каждого Обхода дерево отрезков etree[i], поддерживающее операции изменения элемента и нахождения суммы на интервале. Для каждой вершины сохраним номер Обхода Зла, на котором она лежит, и ее порядковый номер на данном Обходе (при реализации стоит аккуратно обрабатывать случаи с вершинами Пути Добра, поскольку они принадлежат двум Обходам). Тем самым, расстояние между двумя вершинами одного Обхода равно сумме весов ребер соответствующего дерева на интервале с границами, равными порядковым номерам вершин. Аналогично, заведем дерево отрезков gtree и для Пути Добра, разрезав его по первой вершине (для путей, в которых она является внутренней, будем делать два запроса). При этом для каждой пары соседних вершин Пути будем хранить в дереве минимальное из расстояний – расстояние по ребру Пути Добра или расстояние по Обходу Зла. Таким образом, для любых двух вершин Пути Добра, соответствующий запрос к дереву вернет длину (пару чисел) кратчайшего из всех путей между этими вершинами. Данная структура позволяет находить кратчайшее расстояние между двумя произвольными вершинами Пути или одного Обхода за O(_log_(_N_)). Изначально для каждой пары соседних вершин Пути Добра нужно обновить соответствующий элемент дерева значением (_0_, 1).

Теперь рассмотрим запрос на добавление одного гнома на ребро. Для быстрой обработки этого запроса нам придется дополнительно хранить количество гномов gsum[i] на каждой дороге Пути Добра и суммарное число гномов esum[i] на каждом Обходе Зла. Если гном встал на ребро i Пути, то увеличим gsum[i] на 1. Аналогично, если гном встал на ребро Обхода i, то увеличим esum[i] на 1, а так же обновим соответствующее ребру значение в дереве etree[i]. После любого из этих действий потребуется так же записать в дерево gtree новое значение кратчайшего пути между соответствующими соседними вершинами, поскольку оно могло измениться. Заметим, что при удалении гномов с ребра можно проделать обратные операции с той же асимптотикой. Таким образом, запрос на изменение количество гномов на ребре можно обработать за O(_log_(_N_)).

Далее научимся находить кратчайший путь между двумя произвольными вершинами s и t. Создадим вектор вершин Пути Добра sg, до которых можно добраться из s по Обходу Зла, на котором она лежит (соответственно, в sg будет одна или две вершины). Аналогично, вектор tg — вершины Пути Добра, до которых можно добраться из t по Обходу Зла. Рассмотрим объединение векторов tsg = sg + tg. Для каждой вершины u объединения найдем вершину v1, которая первая среди вершин tsg встретится на пути из u, если двигаться по Пути Добра в сторону увеличения индексов вершин (т.е. в том порядке, в котором вершины Пути даны во входных данных). Аналогично, v2 – первая вершина на противоположном направлении. Добавим в список смежности вершины u найденные вершины v1 и v2 вместе с расстояниями до них. Кроме того, так же найдем ребра (расстояния по Обходам Зла) из s в вершины вектора sg, из вершин tg – в вершину t. Если вершины s и t лежат на одном Обходе Зла (и обе не лежат не Пути Добра), то добавим еще прямое ребро из s в t, соответствующее пути по Обходу Зла. Таким образом, мы получили граф, состоящий не более чем из 6 вершин и не более чем из 13 ребер. Запустим алгоритм Дейкстры на этом графе для нахождения кратчайшего пути из s в t. Заметим, что пути исходного графа, соответствующие ребрам нового графа, не пересекаются по внутренним вершинам (кроме, возможно, прямого ребра из s в t). Поэтому для определения лексикографической минимальности достаточно знать только первую внутреннюю вершину на пути, соответствующем какому-либо ребру. Тогда можно, например, добавить еще один параметр для каждого пути нового графа – вектор индексов первых вершин исходного графа при переходах по ребрам нового графа. В этом случае 3 параметра (число гномов, число ребер, вектор индексов) однозначно определят оптимальный путь, по которому будет двигаться Миссия Смерти.

Далее нужно вывести ответ и научиться обрабатывать уничтожение гномов на пути. Восстановим вершины в оптимальном пути. Ребро между каждой парой соседних вершин представляет собой либо путь по Обходу Зла, либо путь между двумя вершинами Пути Добра. Для быстрого поиска гномов, находящихся на Обходах Зла, заведем для каждого Обхода мультисет eset[i] из индексов ребер этого обхода, на которых находятся гномы. Тогда при добавлении гнома на ребро необходимо будет добавить соответствующий индекс в мультисет Обхода. Теперь для удаления гномов с Обхода Зла i, находящихся между ребрами l и r, достаточно найти итератор первого гнома, использовав eset[i]._lower_bound_(_l_) и итерировать, сохраняя полученные позиции гномов в список, пока очередное значение не превысит r. После этого необходимо удалить всех гномов, попавших в список при помощи описанной выше процедуры (аналогично добавлению). Для обработки путей между двумя вершинами Пути Добра, заведем сет gset индексов на Пути, таких что между соседними вершинами, соответствующими индексу, не существует пути, не содержащим гномов. Для поддержания сета необходимо при каждом изменении (добавлении/удалении) гнома добавить проверку: если минимальное расстояние (соответствующее значению в дереве gtree) стало равно 0 (по количеству гномов), то нужно удалить соответствующий индекс из gset, в противном случае – добавить. Тогда, проделав аналогичную процедуру (вызвав gset._lower_bound_ и проитерировав необходимое число раз), мы получим список индексов вершин, проходя через которые мы будем должны уничтожить хотя бы одного гнома на пути к следующей вершине Пути Добра (понятно, что пары вершин, между которыми есть путь, не содержащий гномов, нас не интересуют, ибо Миссия Смерти пройдет по нему, никого не уничтожив). Рассмотрим индекс i этого списка. Если для соответствующей вершины оптимальный путь в следующую вершину Пути Добра лежит через Обход Зла, то есть esum[i] < gsum[i], то необходимо удалить всех гномов с этого Обхода, алгоритмом, описанным выше. В противном случае, достаточно задать gsum[i] = 0 и обновить соответствующее значение в дереве отрезков Пути gtree.

Таким образом, одного гнома с пути, по которому прошла Миссия Смерти, можно удалить за O(_log_(_N_)). Поскольку количество удалений гномов не превосходит количества добавленных гномов (то есть не более Q – количество запросов), то амортизационная сложность одного запроса на обработку Миссии Смерти есть так же O(_log_(_N_)). Итого, общая сложность алгоритма есть O(_log_(_N_) * Q).