1632
правки
Изменения
м
rollbackEdits.php mass rollback
Первая задача решается методом [[Сортировка_слиянием|«разделяй и властвуй»]] {{---}} давайте разделим массив <tex>a[0 \dots n-1]</tex> на 2 массива <tex>a[0\dots\dfrac{n}{2} - 1]</tex> и <tex>a[\dfrac{n}{2} \dots n-1]</tex> и рекурсивно решим задачу для каждого из них. Осталось научиться находить количество искомых пар <tex>(i, j)</tex>, таких что <tex>i < \dfrac{n}{2},\text{ }j \geqslant \dfrac{n}{2}</tex>. Для этого воспользуемся другой известной техникой {{---}} методом двух указателей. Посчитаем массив префиксных сумм для правой половины <tex>pref[i] = \sum\limits_{j=\frac{n}{2}}^{i} a_j</tex> и суффиксных <tex>(suf[i] = \sum\limits_{j=i}^{\frac{n}{2} + 1} a_j)</tex> {{---}} для левой. Заведем два указателя <tex>(p_1</tex> и <tex>p_2)</tex>. Изначально установим <tex>p_1 = \dfrac{n}{2} - l + 1,\text{ }p_2 = \dfrac{n}{2}</tex>. Пока <tex>p_2 - 1> \dfrac{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 - \dfrac{n}{2} + 1) \cdot (\dfrac{n}{2} - p_1)</math>, после чего увеличим <math>p_1</math> на <math>1</math>. Так будем делать, пока <math>p_1 < \dfrac{n}{2}</math>. В конце сложим текущий ответ и ответы для половин массива {{---}} получим ответ на задачу. Время работы такого алгоритма: <tex>T(n) = 2 \cdot T(n / 2) + O(n) = O(n*log(n))</tex>
Вторая задача имеет запросы на изменение и поэтому надо применить динамическую версию «разделяй и властвуй» {{---}} [[Дерево_отрезков._Построение|дерево отрезков]]. Построим дерево отрезков,
Поиск центроида в дереве:
'''int''' <tex>\mathtt{findCentroid}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz, '''int''' tree_size)
max_subtree = -1
'''for''' u : children(v)
'''if''' sz[u] > sz[v] tree_size / 2 '''and''' sz[u] > sz[max_subtree] <font color=green>// считаем sz[-1] = 0 </font >
max_subtree = u
'''if''' max_subtree == -1
return v
'''else'''
'''return''' <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, tree_size)
Шаблон решения произвольной задачи на статическую центроидную декомпозицию:
<tex>\mathtt{solve}</tex>('''int[]''' children[n], '''int''' v, '''int[]''' sz)
c = <tex>\mathtt{findCentroid}</tex>(children, max_subtree, sz, sz[v]) <font color=green>// находим c {{---}} центроид поддерева вершины v </font >
ch = children[c]
<tex>\mathtt{deleteEdges}</tex>(c, children) <font color=green>// удаляем все ребра между вершиной с и детьми, чтобы мы не смогли из детей попасть в с.
'''Деревом центроидов''' (или центроидной декомпозицией, англ. ''centroid decomposition tree'') дерева <math>t</math> называют дерево <math>T(t)</math>, построенное на вершинах дерева <math>t</math> следующим образом:
* Пусть вершина <math>c</math> {{---}} центроид дерева <math>t</math>. Объявим его корнем нового дерева <math>T</math>.
* Пусть при удалении вершины <math>c</math> из дерева <math>t</math> оно распалось на поддеревья <tex>t_1, t_2,\dots, t_k</tex>, тогда детьми вершины c объявим <tex>T(t_1), T(t_tt_2),\dots, T(t_k)</tex>.
}}
=== Свойства центроидной декомпозиции ===
#При проходе по массиву предков фиксированной вершины будет выигрыш в скорости работы, так как весь массив будет лежать непрерывным блоком данных и следовательно будет закэширован
# На массиве предков можно строить различные структуры данных (такие как, например, дерево отрезков) для быстрого (в случае с деревом отрезков <math>O(log(\log(n)))</math> на запрос) поиска предка с необходимыми свойствами. Так, например, в описанной выше задаче про помеченные вершины наибольшего общего предка можно искать методом двоичных подъемов за <math>O(\log(\log(n))</math> на запрос, так как размер массива предков есть <math>O(\log(n))</math> (по свойству <math>1</math> центроидной декомпозиции). Используя эту оптимизацию можно получить время <math>O(\log(n)) + O(\log(\log(n)) = O(\log(n))</math> на запрос нахождения ближайшей помеченной вершины. Чтобы добиться улучшенной асимптотики для запросов изменения можно хранить дерево отрезков на каждом из путей <math>p[v]</math>, в каждой вершине которого хранить двоичное дерево поиска и поддерживать отложенные операции. Тогда ответ на эти запросы будет занимать <math>O(\log(n) \cdot \log(\log(n))</math> времени.
==См. также==
