Изменения
Нет описания правки
}}
Для начала решим обе задачи.
Первая задача решается методом [[Сортировка_слиянием|qevidedivide &conqure conquer (рус. разделяй и властвуй)]] {{---}} давайте разделим массив <tex>a[0 \dots n-1]</tex> на 2 массива <tex>a[0\dots\frac{n}{2} - 1]</tex> и <tex>a[\frac{n}{2} \dots n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \frac{n}{2}, j \geqslant \frac{n}{2}</tex>. Для этого воспользуемся другой известной техникой {{---}} методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных (<tex>suf[i] = \sum_{j=i}^{\frac{n}{2} + 1} a_j</tex>) {{---}} для левой. Заведем два указателя (<tex>p_1</tex> и <tex>p_2</tex>). Изначально установим <tex>p_1 = \frac{n}{2} - l + 1, p_2 = \frac{n}{2}</tex>. Пока <tex>p_2 - 1> \frac{n}{2}</tex> и
<tex>pref[p_2] + suf[p_1] > W </tex> будем уменьшать <math>p_2</math> на <math>1</math>. Если после этого <math>pref[p_2] + suf[p_1] \leqslant W</math>, то к ответу прибавим <math>(p_2 - \frac{n}{2} + 1) * (\frac{n}{2} - p_1)</math>, посго, увеличим <math>p_1</math> на <math/math>. Так будем делать, пока <math>p_1 < \frac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива {{---}} получим ответ на задачу. Асимптотика такого алгоритма: <tex>T(n) = 2 * T(n / 2) + O(n) = O(n)</tex>
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию qevidedivide &conqure conquer {{---}} [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
поддерживающее 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>). Для этого внутри бинарного поиска каждый раз делаем запрос на поиск минимума в дереве отрезков.
== Динамическая центроидная декомпозиция (дерево центроидной декомпозиции) ==
Теперь вернемся ко второй задаче введения. Для ее решения мы пользовались динамичекой версией devidedivide &conqure conquer {{---}} деревом отрезков. В предыдущем пункте мы определили статический оналог devidedivide &conqure conquer для дерева. Теперь обобщим этот метод для динамических задач.
{{Определение
|definition=
