186
правок
Изменения
→Введение
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevide&conqure - [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
поддерживающее 2 вида запросов : присвоение в точке и минимум на отрезке. Изначально сделаем так, чтобы дереву отрезков соответствовал массив <math>b[]</math>, такой что <tex>b[i] = 0</tex>, если в i-м городе принимает госпиталь и <tex>b[i] = 1</tex> иначе. Когда в каком-то городе открывается/закрывается госпиталь - делаем запрос на изменение в дереве отрезков. Когда требуется узнать ближайщий госпиталь к <math>i</math>-му городу, можно воспользоваться одной из следующих идей :
а) (<tex>O(n*\dot log^2(n)</tex>) Бинарным поиском ищем ближайший слева и ближайший справа к i-му городу госпиталь (такой город <math>j</math>, что <math>min(i...j) = 1</math>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков. б) (<tex>O(n*\dot log(n)</tex>) Будем одним спуском/подъемом по дереву определять, куда нам нужно идти (в левое или правое поддерево), тем самым делая одновоременно и бинарный поиск, и спуск/подъем по дереву.
== Статическая центроидная декомпозиция ==
