Всем привет, Codeforces! Я давно хотел написать какой-нибудь образовательный блог, но никак не мог найти для этого тему. И недавно я вспомнил, что на Codeforces нет толкового блога по одной из моих любимых тем: технике "разделяй и властвуй". Поэтому я хочу рассказать о ней. План будет примерно такой:
1) Разделяй и властвуй. Что это за техника такая и для чего она нужна. Пример. 2) Dynamic connectivity offline при помощи разделяй и властвуй. Разделяй и властвуй dp оптимизация. 3) Расскажу о методе, который я придумал самостоятельно: разделяй и властвуй по запросам. В этом случае мы делим не только массив, но и запросы на группы.
Итак, поехали.
Сначала о том, что это за техника такая. Суть состоит примерно в следующем: пусть у нас есть, скажем, массив. Тогда, если мы умеем вычислять ответ для двух его частей, и умеем из ответов по двум частям получать ответ для целого массива, то можно применить технику разделяй и властвуй. Давайте разберем ее на самом простом примере: сортировке слиянием.
В сортировке слиянием у нас есть массив из $$$n$$$ элементов, далее, для простоты, чисел. Чтобы отсортировать подмассив $$$[l .. r]$$$, мы сортируем подмассивы $$$[l .. m]$$$ и $$$[m + 1 .. r]$$$, где $$$l \le m \le r$$$, после чего сливаем два отсортированных массива в один. Рассмотрим, как сделать это проще всего.
В самом деле, пусть у нас есть два массива. Мы знаем, что они отсортированы, например, по неубыванию. Тогда, чтобы слить два массива в один, можно применить следующий алгоритм:
1) Если первый массив пуст, то добавить второй массив к массиву с результатом и завершить работу. 2) Если второй массив пуст, то добавить первый массив к массиву с результатом и завершить работу. 3) Если оба массива не пусты, то взять наименьший из двух первых элементов массивов, добавить его к ответу и удалить из изначального массива.
Конечно же, удалять из начала массива не следует, а гораздо лучше хранить указатель на текущий элемент, который мы рассматриваем. Если вы пишете на С++, рекомендую использовать функцию std::merge вместо этого рукописного алгоритма. Но все-таки иногда полезно понимать, как он работает.
Теперь будем действовать рекурсивно: напишем функцию sort(l, r), которая сортирует отрезок с l по r:
sort(l, r):
if l == r:
return
m = (l + r) / 2
sort(l, m)
sort(m + 1, r)
merge(l, m, m + 1, r)
Итак, теперь давайте оценим время работы такой сортировки. Кажется логичным делить массив примерно пополам, то есть $$$m = \lfloor \frac{l + r}{2} \rfloor $$$. Посмотрим, сколько операций выполнит наш алгоритм. Для простоты положим число элементов массива $$$n = 2^k$$$. Тогда ясно, что на объединение подмассивов размера $$$1$$$ будет потрачено суммарно $$$O(n)$$$ операций, на объединение подмассивов размера $$$2$$$ будет потрачено $$$O(n)$$$ операций, далее размера $$$4$$$, $$$8$$$ и так далее.
Отсюда видно, что при объединении каждого из <<слоев>> алгоритм выполнит $$$O(n)$$$ действий, а поскольку таких слоев $$$k$$$, то итого это работает за $$$O(nk) = O(n \log n)$$$. Такая конструкция напоминает дерево отрезков. Впрочем, это почти оно и есть. Например, если в дереве отрезков в каждой вершине хранить отсортированный подотрезок, соответствующий этой вершине, то количество памяти, затраченной на это, будет $$$O (n \log n)$$$, и время построения тоже (можете доказать это самостоятельно в качестве упражнения).
Также на методе разделяй и властвуй основаны некоторые другие алгоритмы, такие как, например, dynamic connectivity offline. Задача состоит в том, чтобы обрабатывать в offline такие запросы:
1) Добавить ребро в граф. 2) Удалить ребро из графа. 3) Проверить, лежат ли две вершины в одной компоненте связности.
Данная тема может быть немного сложновата для новичков, поэтому если будет сложно, можете пропустить. Поскольку я не смог быстро найти англоязычные материалы по данному методу, то опишу его тут, хотя он довольно хорошо известен.
Задача не очень сложно решается при помощи SQRT-декомпозиции, но я расскажу решение за $$$O(q \log n \log q)$$$.
Пусть в графе $$$n$$$ вершин и $$$q$$$ запросов, более того, граф изначально пуст. Если это не так, то просто добавим в начало запросы на добавление изначальных ребер.
Теперь определим для каждого ребра время жизни: непрерывный отрезок из номеров запросов, в течение которого существует это ребро. Каждому запросу проверки соответствует какое-то время: по сути, просто его номер на входе.
Теперь построим такое дерево отрезков: в нем будут храниться номера ребер. Изначально это дерево отрезков пусто. Теперь для ребра со временем жизни [l .. r] напишем вот такое добавление в дерево отрезков:
add(v, tl, tr, l, r):
if l > r:
return
if tl == l && tr == r:
tree[v].insert(edge)
return
tm = (tl + tr) / 2
add(v * 2, tl, tm, l, min(r, tm))
add(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)
То есть мы написали дерево отрезков, которое очень похоже на то, что присваивает на отрезке, только без ленивого проталкивания. Что же мы получили в итоге? Можно заметить, что теперь отрезок [l .. r] оказался разбит на $$$O(\log n)$$$ отрезков из дерева отрезков. Давайте теперь запустим поиск в глубину таким образом:
dfs(v, tl, tr):
if tl == tr:
answer_query(tl)
return
tm = (tl + tr) / 2
edge_set.insert_edges(tree[v])
dfs(v * 2, tl, tm)
dfs(v * 2 + 1, tm + 1, tr)
edge_set.erase_edges(tree[v])
Теперь заметим, что, когда мы придем в лист, отвечающий отрезку [w .. w], то в $$$edge$$$_$$$set$$$ окажутся те и только те ребра, которые были <<живы>> в момент времени $$$w$$$, то есть по сути мы получим список ребер, которые были в момент времени $$$w$$$.
Итак, если бы мы умели по списку ребер быстро отвечать на запрос, то мы бы получили готовое решение. К сожалению, в обычный СНМ можно только добавлять ребра, а при таком решении нам еще нужно их удалять. Поэтому необходимо применить персистентный СНМ. Не пугайтесь, он работает совсем несложно. Давайте напишем обычный СНМ с, например, ранговой эвристикой, или эвристикой по размеру. Тогда при каждом добавлении ребра просто поменяется непосредственный предок одной из вершин, и поменяется ранг / размер поддерева одной из вершин. Давайте в специальный массив после каждого добавленного ребра добавлять информацию о том, в какой вершине и какие изменения были совершены. Тогда мы сможем отменять последнее добавление ребра за $$$O(\log n)$$$. В принципе, нам этого достаточно.
Оценка асимптотики теперь ясна: добавление одного ребра в дерево отрезков занимает $$$O(\log q)$$$ операций, а весь dfs займет $$$O(q \cdot t_1 + S \cdot t_2)$$$, где $$$t_1$$$ -- время на ответ на запрос, $$$S$$$ -- суммарное количество ребер, которое хранится в дереве отрезков, а $$$t_2$$$ -- время добавления и удаления одного ребра. Учитывая, что $$$t_1 = O(\log n)$$$, $$$S = O(q \log q)$$$, а $$$t_2 = O(\log n)$$$, приходим к требуемой асимптотике.
Довольно непростая задача на эту тему: https://mirror.codeforces.com/problemset/problem/813/F
Теперь вкратце упомяну ДП оптимизацию разделяй и властвуй. Она позволяет сократить время работы некоторых ДП при некоторых условиях. На английском языке про это можно почитать, например, тут: https://cp-algorithms.com/dynamic_programming/divide-and-conquer-dp.html
Задача на эту тему: https://mirror.codeforces.com/problemset/problem/868/F
А теперь давайте приступим к самому интересному: разделяй и властвуй по запросам. Этот метод я придумал самостоятельно, когда решал одну задачу (о ней несколько позже). Не знаю, первый ли я, кто придумал этот метод, но честно говоря, я его раньше не видел. Если его где-то описали до меня то напишите мне об этом в комментарии, пожалуйста.
Этот метод чем-то похож на дерево отрезков, которое хранит запросы, но, как мне кажется, несколько проще в написании и понимании.
Разберем следующую задачу: https://mirror.codeforces.com/problemset/problem/763/E
Будем действовать так: сначала построим разделяй и властвуй на массиве. С его помощью мы можем построить СНМ для каждого рассматриваемого отрезка, и также можем научиться находить ответ на префиксе и суффиксе каждого отрезка: в самом деле, это просто количество различных компонент связности на отрезке. Сделать это можно хоть в лоб, добавляя по одной вершине в СНМ.
Но как же нам отвечать на запросы? А вот тут в игру и вступает разделяй и властвуй по отрезкам. Давайте при рассмотрении отрезка [l .. r] отвечать только на такие запросы [ql .. qr], что $$$ql \le m < qr$$$, то есть только на такие запросы, левая граница которых лежит на отрезке [l .. m], а правая граница которого лежит на отрезке [m + 1 .. r]. Ясно, что остальные запросы будут рассмотрены либо в [l .. m], либо в [m + 1 .. r].
Теперь отвечать на такие запросы становится несложно: можно взять два СНМа, соединить их в один, и провести ребра на границе. Так как $$$k$$$ невелико, таких соединений будет немного.
Таким образом, получили давольно быстрое и красивое решение этой задачи. Видно, что оно не использует дерево отрезков по запросам.
Напоследок рассмотрим еще одну задачу, которую можно решать при помощи этого метода: https://mirror.codeforces.com/gym/101590/problem/D
К сожалению, в ней только русское условие, так что расскажу, что необходимо сделать:
Дан массив из $$$n$$$ троек чисел, а также число $$$D$$$. Также даны $$$q$$$ запросов с отрезками $$$l_i$$$ и $$$r_i$$$. Необходимо на отрезке выбрать из каждой тройки по одному числу так, чтобы сумма была как можно больше, но при этом делилась на $$$D$$$. Например, если даны тройки (1, 2, 3), (4, 5, 6) и (1, 7, 8), и $$$D = 8$$$, то можно выбрать $$$3$$$, $$$6$$$ и $$$7$$$.
$$$n \le 50000, q \le 300000, D \le 50$$$.
По этой задаче понятно, почему дерево отрезков не всегда лучше. В самом деле, давайте попробуем написать дерево отрезков, в каждой вершине которого будет лежать ДП на этом отрезке. Но тогда оценим время работы. Ясно, что ДП будет одномерным: $$$dp[r]$$$, где $$$r$$$ от слова remainder -- остаток. Нетрудно посчитать для каждого остатка, чему будет равна максимальная сумма.
Но вот незадача: когда дело доходит до дерева отрезков, выясняется, что объединение двух ДПшек работает за $$$O(D ^ 2)$$$, и дерево отрезков просто не пройдет!
Но тут можно применить разделяй и властвуй по запросам: отдельно посчитаем ДП для левой половины, и отдельно посчитаем ДП для правой половины. Причем будем хранить ДП для каждого суффикса левого отрезка и для каждого префикса правого отрезка (напомню, что ДП это массив из $$$D$$$ чисел). Будем отвечать только на те запросы, которые пересекают оба отрезка. Для этого достаточно просто взять ДП соответствующего суффикса, и ДП соответствующего префикса, и перебрать остаток $$$r$$$ префикса (остаток суффикса будет равен $$$D - r$$$). Таким образом, получили решение за $$$O(q \cdot D + n \cdot \log n \cdot D)$$$.
Надеюсь, вам понравился этот блог. Это мой первый образовательный блог, и я старался писать как можно понятнее. Если у вас остались вопросы, можете смело оставлять их в комментариях.
