Изменения

Перейти к: навигация, поиск

Centroid decomposition

4 байта убрано, 15:32, 17 июня 2017
Нет описания правки
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» {{---}} [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
поддерживающее 2 вида запросов: присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b</math>, такой что <tex>b_i = 0</tex>, если в i-м городе принимает госпиталь и <tex>b_i = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь {{---}} делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей:
а) * (<tex>O(n \cdot log^2(n)</tex>) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город <math>j</math>, что <tex>\min\limits_{k=i..j}b_k= 1</tex>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. б) * (<tex>O(n \cdot log(n)</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.
== Статическая центроидная декомпозиция ==
Анонимный участник

Навигация