0:00 Занятие начинается с разбора контеста по деревьям отрезков (лектор называет его «разбором в порядке возрастания сложности»). Условия задач звучат устно и напоминаются кратко; ниже они записаны так, как их пересказал лектор. Те задачи, которые были подробно разобраны на лекциях, даются только ссылкой на идею.
0:07 Решение сводится к одной фразе: задачу решают независимо по каждому биту. Для младшего бита, для следующего и так далее строится своё дерево отрезков, в вершине которого хранится информация для нулей и единиц. Ответ получается объединением результатов по всем битам. Тот же приём используется для любых побитовых операций: операции над разными разрядами между собой не связаны.
0:23 Задача I разобрана на лекции. 3:36 Задача J — «напишите многомерный Фенвик» — тоже: многомерное дерево Фенвика обсуждалось на занятии, поэтому здесь не разбирается.
0:45 Что хранить в дереве. В дереве отрезков хранятся индексы копируемых элементов второго массива. Если в позиции записано число $j$, значит, в этой позиции первого массива сейчас лежит $b_j$; значение $-1$ означает, что позиция не менялась и там осталось исходное число.
1:20 Чтобы скопировать отрезок, на заданном диапазоне первого массива нужно проставить арифметическую прогрессию с шагом $1$. Например, при копировании первых трёх элементов второго массива проставляются значения $0, 1, 2$; при копировании элементов со второго по четвёртый — $1, 2, 3$. 1:43 Тогда запрос в первом массиве возвращает индекс элемента второго массива: если он равен $-1$, берём исходное число, иначе берём число из второго массива по этому индексу.
1:58 Проставление арифметической прогрессии разбиралось на предыдущей лекции. Так как шаг всегда один, в массовой операции достаточно хранить только первое число прогрессии (оно не всегда ноль).
2:27 Задача разбиралась на лекции; лектор напоминает, что её можно решать двумя способами.
3:54 В задаче три операции на дереве отрезков. Первая — прибавление числа на отрезке. Вторая — прибавление «шатра»: в центре отрезка прибавляется большое значение $X$, а в обе стороны оно убывает с шагом $d$. Фактически это две арифметические прогрессии: одна с шагом $+d$, вторая с шагом $-d$, причём вторая начинается с максимального значения $X$, а начало первой вычисляется (4:32).
4:43 Прибавлять арифметическую прогрессию на отрезке умеем; остаётся «докрутить» операцию обычного прибавления. Лайфхак: представить обе операции как одну и ту же массовую операцию. 4:58 Прибавление числа на отрезке — это прибавление арифметической прогрессии с шагом ноль. Поэтому все операции в дереве — это прибавление арифметической прогрессии, а запрос $get$ делается как обычно. 5:16 Участник уточняет, что шаг прогрессии не обязан быть единицей; лектор отвечает, что от этого только проще — всё сводится к прибавлению арифметической прогрессии.
5:53 Используется сортировка подсчётом: на отрезке считаем количество символов каждого вида, затем присваиваем отрезки нужных символов. Лектор предлагает сравнить два варианта (6:02):
7:11 Во втором варианте для запроса сначала в каждом из деревьев выполняется $get$ — сколько символов этого вида на отрезке; затем в каждом дереве отрезок зануляется; затем в нужных деревьях нужный отрезок заполняется единицами.
7:37 Асимптотика. В первом варианте каждый запрос стоит $26 \cdot \log n$ на каждую операцию (в каждой посещённой вершине пересчитываются все $26$ чисел), а таких операций тоже $26$; итого размер алфавита в квадрате на логарифм: $O(26^2 \log n)$. Во втором варианте нет штрафа за пересчёт всех значений в каждой вершине: получается $O(26 \log n)$ на запрос. Второй вариант заходит точно и проще пишется (нули и единицы); первый, по словам лектора, тоже можно «упихать».
8:38 Урок. Иногда стоит следить за тем, сколько стоит одно слияние (merge) в вершине: если оно долгое, это влияет на асимптотику.
8:52 Это учебная задача на Merge Sort Tree, которая разобрана на лекции; не обсуждается. (Merge Sort Tree — дерево отрезков, в вершине которого лежит отсортированный массив её отрезка; сокращённо MST.)
9:14 Запросы: прибавить число на отрезке и найти $\gcd$ на отрезке.
9:24 Идея. НОД набора чисел равен НОД любого одного числа из набора и всех чисел его разностного массива: $$\gcd(a_l, a_{l+1}, \dots, a_r) = \gcd\bigl(a_l,\ a_{l+1} - a_l,\ \dots,\ a_r - a_{r-1}\bigr).$$ Пример лектора: числа $7, 21, 49$ при разностях $14, 28$ дают $\gcd = 7$; если к разностям добавить, например, $49$, НОД остаётся равным $7$ (9:35–10:08).
10:17 Решение. Храним два дерева отрезков.
push здесь придумать нельзя.11:55 Запросы: взять числа на отрезке по модулю, присвоить значение, найти сумму на отрезке. Лектор напоминает идею, разобранную на лекции (12:14):
Ключевое наблюдение. При взятии числа по модулю есть два варианта: либо оно не изменилось (было меньше модуля), либо уменьшилось хотя бы вдвое. Значит, без присваиваний каждое число изменилось бы не более $\log C$ раз ($C$ — максимальное значение), и всего изменений было бы не более $n \log C$.
12:54 Присваивание ничего не ломает. Присваиваний не более $Q$, поэтому в структуру за всё время попадёт не более $N + Q$ чисел ($N$ — исходные, $Q$ — верхняя граница тех, что будут присвоены), и каждое из них сократится не более $\log C$ раз. Итого операций модуля, меняющих числа, не более $(N+Q)\log C$.
13:29 Как реализовать. Есть два варианта.
15:17 Есть набор отрезков. В запросе приходит набор точек, нужно найти число отрезков, накрывающих хотя бы одну из них (15:33).
15:42 Идея. Заранее посчитать для каждой точки, сколько отрезков её покрывает (это делается сканирующей прямой). Но просто сложить эти числа нельзя: отрезок, накрывающий сразу две точки, посчитается дважды. Поэтому идём по точкам слева направо и в каждой считаем только новые отрезки (16:51) — те, которые накрывают текущую точку и не накрывают предыдущую. Если отрезок накрывает текущую точку и уже был учтён, он гарантированно накрывает и предыдущую.
17:28 Новые отрезки = (все отрезки, накрывающие текущую точку) минус (отрезки, накрывающие весь промежуток между предыдущей и текущей точкой). Количество накрывающих точку известно, остаётся научиться отвечать на запрос: сколько отрезков накрывают весь диапазон $[L, R]$ (17:53).
18:10 Как отвечать. Отсортируем отрезки по левой границе и выпишем их правые границы в этом порядке (18:19). Тогда запрос «накрывают $[L, R]$» — это отрезки с левой границей $\le L$ (префикс этого массива, находится бинарным поиском) и правой границей $\ge R$ (19:18). Остаётся посчитать на префиксе количество чисел $\ge R$: это делается Merge Sort Tree либо Wavelet Tree (19:48). Вейвлет асимптотически быстрее, но MST тоже заходит.
22:05 Нужно найти $k$-е по порядку число на отрезке. Первый шаг — бинарный поиск по ответу: нужно отвечать на вопрос «сколько на отрезке чисел меньше $x$».
23:29 Лектор считает задачу «абсолютной халявой», хотя её сдали мало людей из-за тяжёлых условий.
24:19 Это обычное дерево отрезков, в котором в вершине хранятся максимум и исторический максимум на отрезке.
24:44 В массовом обновлении без исторического максимума хранилось бы одно число: сколько добавить на отрезке — назовём его $add$. Теперь добавляется второе — $hadd$: максимальное значение добавки с момента предыдущего push (24:59). Когда мы делаем push, исторический максимум «перетекает» в детей, и обе добавки обнуляются. Пока push не делается, при добавлении $x$ мы увеличиваем $add$ на $x$ и обновляем $hadd = \max(hadd,\ add)$.
25:31 Push. Лектор описывает его словами: при проталкивании сначала используем историческую добавку, затем обычную; ниже то же самое записано точно.
push (то есть максимум из $0$ и всех частичных сумм). Чтобы применить к вершине пакет «добавка $a$, наибольшая частичная сумма которой $h$», достаточно четырёх присваиваний (порядок важен — сначала история, потом текущие значения):
$$hmx \gets \max(hmx,\ mx + h),\quad mx \gets mx + a,\quad hadd \gets \max(hadd,\ add + h),\quad add \gets add + a.$$
push применяет к обоим детям пакет $(add_v,\ hadd_v)$ и обнуляет $add_v$, $hadd_v$. Обычная операция «прибавить $x$ на отрезке» применяет к полностью покрытой вершине пакет $(x,\ \max(x, 0))$.
struct SegTree {
int n;
vector<long long> mx, hmx, add, hadd;
// ... build: mx[v] = hmx[v] = a[l] в листе; pull: максимумы детей ...
void apply(int v, long long a, long long h) {
hmx[v] = max(hmx[v], mx[v] + h); // сначала история
mx[v] += a; // потом текущее значение
hadd[v] = max(hadd[v], add[v] + h);
add[v] += a;
}
void push(int v) {
if (add[v] == 0 && hadd[v] == 0) return;
for (int c : {2 * v, 2 * v + 1}) apply(c, add[v], hadd[v]);
add[v] = hadd[v] = 0;
}
// update: если вершина целиком в отрезке — apply(v, x, max(x, 0LL)); иначе push, рекурсия, pull
// query: исторический максимум — hmx[v] у полностью покрытых вершин, push при спуске
};25:57 Смысл задачи — показать, что в массовых операциях могут лежать нетривиальные величины и push может выглядеть нетривиально.
push. Если бы на моменте «+5» произошёл push, пятёрка уже ушла бы вниз.27:24 Сначала решаем задачу на всём массиве. Монеты рассматриваем в порядке возрастания номинала (порядок монет в массиве ни на что не влияет). Поддерживаем инвариант: умеем набирать ровно суммы от $1$ до $x$ и никакие другие. Изначально $x = 0$.
28:21 Рассмотрим очередную монету $y$.
30:10 Запросы на отрезке. Начинаем с $x = 0$. На каждом шаге делаем запрос «сумма всех монет на отрезке со значением $\le x + 1$» (30:31) — это все монеты, которые могут пригодиться. Если сумма оказалась больше $x$, то $x$ становится равным этой сумме (30:54). Важно присваивание «=», а не «+=»: эта сумма уже включает монеты, использованные ранее (31:27). Если $x$ не изменился, ответ $x + 1$ (31:47).
32:02 Сколько шагов. Не больше $2\log$ (по порядку величины — логарифм): пусть $x$ перешло в $x'$, затем в $x''$. В момент $x'$ уже использованы все монеты $\le x+1$; значит, при втором переходе добавилась монета, большая $x + 1$, и новая сумма не меньше $x + (x+1)$, то есть $\ge 2x$. За любые два перехода число удваивается, поэтому их не более $2\log C$ (32:19–32:56). Лектор отмечает, что эта оценка очень грубая.
33:07 Сумма монет $\le x+1$ на отрезке — это запрос «сумма чисел на отрезке не больше $v$»: MST или Wavelet Tree. MST проще пишется; вейвлет на практике ускоряет в два–три раза, а не в десятки (33:21–33:49).
38:15 Перефразировка. Очень важный шаг. Когда мы убираем карту, мы не вставляем её сразу в колоду, а откладываем в карман. Теперь за одно действие можно взять либо верхнюю карту колоды, либо любую карту из кармана. Позже строится последовательность действий, показывающая, что формулировки эквивалентны.
39:09 Жадность. Если нужная карта ещё лежит в колоде, берём карты сверху и откладываем их в карман, пока не получим нужную. Если нужная карта уже когда-то откладывалась, достаём её из кармана за одно действие. Так жадно симулируется весь порядок получаемых карт; ответ без восстановления — длина получившегося массива действий (40:48).
39:52 Пример. Колода $1\ 4\ 3\ 5\ 2$, запросы $4, 5, 3, 4$. Идём до четвёрки: взяли $1$ и $4$. Хотим пятёрку: идём до пятёрки, выкидывая $3$ и $5$ (то есть откладываем их в карман). Тройка уже откладывалась — берём за одно действие. Четвёрка тоже откладывалась — берём за одно действие.
40:57 Восстановление: куда вставлять карту. Чтобы понять, куда в колоду надо сунуть карту, нужно посмотреть, когда она понадобится в следующий раз. Берём два её соседних вхождения в последовательность запросов и считаем количество различных чисел между ними (41:07–41:28). Ровно эти числа формируют «шапку» колоды до следующего появления нашей карты: они обязаны лежать выше (мы встретили их раньше), и ничего другого выше быть не может, иначе нам пришлось бы перебирать другие карты до нужной. Поэтому карту нужно вставить на глубину, равную числу различных на отрезке. Количество различных на отрезке считается MST или Wavelet Tree (41:52–42:06).
42:16 Другой взгляд: в каждый момент карты в колоде отсортированы по моменту, когда они в следующий раз будут использованы. Только что использованная карта должна лечь после тех, которые понадобятся раньше неё — отсюда тоже получается «число различных на отрезке» (42:25–42:55).
44:50 Проверка корректности. Строим минимальный возможный загаданный параллелепипед: по каждой оси берём минимум и максимум среди зелёных точек (независимо по каждой оси). Линейным проходом проверяем красные точки: если хотя бы одна попала внутрь, исходные данные некорректны (45:14).
46:19 «Обязательно входит». Точка обязательно входит, если лежит в минимальном параллелепипеде (за $O(1)$ проверяется).
46:48 Различаем «обязательно не входит» и «может». Представим, что запрошенная точка тоже зелёная, и расширим минимальный параллелепипед до охватывающего зелёные точки и новую (по каждой оси берём минимум и максимум трёх значений). Если в расширенном параллелепипеде есть красная точка, то синяя зелёной быть не могла: «не может входить ни в какой загаданный». Если красных точек в нём нет, ответ «может» (47:24–47:40).
47:47 Итак, нужно отвечать на запрос «есть ли красные точки в трёхмерной области». В общем случае это сложно, но здесь любая запрошенная область содержит минимальный параллелепипед (он известен заранее и константен) (48:04).
48:41 Разбиение на восемь частей. Область (расширенный параллелепипед минус минимальный) разбивается на восемь параллелепипедов: берём угол минимального параллелепипеда и противоположный угол расширенного и строим параллелепипед на этих двух точках. Всего восемь таких пар, и в объединении они дают расширенный параллелепипед (48:56–49:32). Нам достаточно, что красная точка нашлась хотя бы в одной из частей.
49:48 Оффлайн по группам. Для каждого запроса получаем по одному параллелепипеду в каждую из восьми групп, и в каждой группе у всех параллелепипедов общий угол — угол минимального параллелепипеда (50:08). Именно этот факт позволяет отвечать на все запросы группы в оффлайне.
51:58 Ответ на запросы одной группы. Пусть общий угол перенесён в начало координат: нужно для каждого параллелепипеда с одним углом в $(0,0,0)$ понять, есть ли в нём красные точки (52:07). Выбираем одну из осей и запускаем по ней сканирующую прямую: события — «добавляется точка» и «закрывается параллелепипед» (52:29). После этого все запросы двумерные: добавление точки на плоскость и проверка, есть ли в области с углом в $(0,0)$ точки (52:46).
53:05 Двумерный запрос решается одномерным деревом отрезков: по каждой строке храним самую левую точку (изначально $+\infty$). При добавлении точки делаем min= в точке. Чтобы проверить область, берём минимум на отрезке строк и сравниваем его с правой границей области (53:23–53:58).
55:32 Склеивать ответы не нужно. Запрос разбит на восемь частей, но объединять результаты не требуется: если в какой-то части нашлась красная точка, ответ записывается сразу в нужную позицию массива ответов (55:41–56:20). Лектор отмечает, что задача — скорее на реализацию, чем на идею (56:34).
57:03 На этом разбор окончен; лектор напоминает, что остальные задачи контеста по идее несложные и пишутся легко, и объявляет начало лекции.
57:39 Лекцию читают два лектора по очереди. Первая часть — основы: BFS, алгоритм Дейкстры с доказательством, приёмы вокруг BFS и алгоритм Флойда. Вторую часть (Форд–Беллман, отрицательные циклы и неявные графы) рассказывает второй лектор после перерыва.
58:51 Сначала лектор «просто повторяет, как устроен BFS» (без доказательства), затем разбирает Дейкстру, и уже с доказательством становится ясно, как BFS и Дейкстра связаны (59:00). Дальше — приёмы для BFS, затем Флойд, а потом второй лектор покажет поиск отрицательных циклов и ещё несколько задач на кратчайшие пути (59:09–59:17). Лектор предупреждает, что доказательства «будут на зачёте» (59:49).
1:00:12 Обозначения. Есть стартовая вершина $S$, рёбра имеют длину один (граф пока считается неориентированным). Массив $D$ — это расстояния, которые мы подсчитываем; $\mathrm{dist}(v)$ — настоящее (оптимальное, кратчайшее) расстояние, известное «оракулу». Изначально $D[S]=0$ (1:00:26–1:00:47).
1:01:25 В очереди BFS хранятся вершины $v_1,v_2,\dots,v_k$. Мы достаём первую вершину и помечаем её; пометка означает, что расстояние до неё больше не пересчитывается — мы утверждаем, что оно оптимально. После этого релаксируем её соседей (1:01:46–1:02:08).
1:02:16 Утверждение. Расстояния, записанные для вершин очереди, не возрастают в обратную сторону, то есть не убывают от начала к концу: $D[v_1]\le D[v_2]\le\dots$ (1:02:25–1:02:39). Доказывается индукцией (1:02:39).
1:04:22 Значит, расстояния в очереди всегда по неубыванию, и вершины достаются в порядке неубывания расстояний. Лектор подчёркивает, что это не доказательство корректности BFS, а замечание; корректность потом сводится к Дейкстре, потому что мы гарантировали: из очереди всегда достаётся наименьший элемент (1:04:47–1:05:20).
1:05:22 Для Дейкстры нужно множество, из которого можно доставать минимум «вручную»; в BFS ребра весом один позволяют обойтись обычной очередью (1:05:22–1:05:39). Первый способ — set пар $(D[v],\,v)$ — расстояние, затем сама вершина (1:05:48–1:06:06).
1:06:06 Вопрос лектора: можно ли вызвать erase для значения, которого в множестве нет? Ответ — можно, ошибки не будет (1:06:13). Поэтому релаксация записывается так: если $D[u]>D[v]+c$, то удаляем из множества пару $(D[u],u)$ (она может и отсутствовать), присваиваем $D[u]$ новое значение и вставляем пару заново (1:06:25–1:07:18).
set все расстояния, лишь бы не удалять отсутствующие элементы. Так писать не нужно: erase несуществующей пары безопасен. Про priority_queue лектор скажет отдельно.// Дейкстра на set: храним пары (расстояние, вершина), при улучшении удаляем старую пару
vector<ll> dijkstra_set(int n, const vector<vector<pair<int,int>>>& g, int s) {
vector<ll> d(n, INF);
set<pair<ll,int>> q;
d[s] = 0; q.insert({0, s});
while (!q.empty()) {
int v = q.begin()->second;
q.erase(q.begin()); // вершина помечена: d[v] окончательно
for (auto [u, w] : g[v])
if (d[u] > d[v] + w) {
q.erase({d[u], u}); // erase несуществующей пары безопасен
d[u] = d[v] + w;
q.insert({d[u], u});
}
}
return d;
}1:07:40 Алгоритм — по аналогии с BFS: тот же пересчёт, а то, что каждый раз берётся минимум, обеспечиваем вручную.
1:08:12 Утверждение: в тот момент, когда вершину достают из очереди и помечают, в ней записано корректное значение: $D[v]=\mathrm{dist}(v)$ (1:08:12–1:08:29). Доказываем индукцией по числу вынутых вершин.
1:08:29 Пусть уже вынуто $k$ вершин и для них инвариант выполнен. Достаём $(k+1)$-ю вершину $U$ — минимум очереди (1:08:36–1:08:45). Рассмотрим множество помеченных вершин; в нём лежит $S$, а $U$ — вне него (1:09:04–1:09:20). Возьмём кратчайший (оптимальный) путь из $S$ в $U$. Он идёт сначала по помеченным вершинам, а затем впервые заходит в непомеченную вершину — назовём её $X$, её предшественника на пути — $Y$ (1:09:20–1:10:05; позже, в 1:13:17–1:13:23, лектор повторяет определение: $X$ — первая непомеченная вершина кратчайшего пути из $S$ в $U$).
1:10:05 Выпишем простые факты об этих вершинах.
1:16:20 В реализации на set в очереди не более $n$ вершин, достаём по одной — $n\log n$, плюс $m$ релаксаций, каждая за $\log n$ (1:16:20–1:16:52):
$$O\bigl((n+m)\log n\bigr).$$
Если граф полный ($m\approx n^2$), получается $O(n^2\log n)$, и этот логарифм «не к месту» — релаксация слишком долгая (1:16:52–1:17:19).
1:17:19 Как сделать релаксацию за $O(1)$, а минимум искать подольше. Оставим единственный массив расстояний; минимум будем искать обычным проходом по массиву, не забывая, что помеченные вершины пропускаются (1:17:19–1:18:18). Тогда релаксация — просто присваивание за $O(1)$, а минимум в массиве длины $n$ ищется $n$ раз: $$O(n^2+m).$$
// Дейкстра за O(n^2 + m): минимум ищем проходом по массиву
vector<ll> dijkstra_n2(int n, const vector<vector<pair<int,int>>>& g, int s) {
vector<ll> d(n, INF);
vector<char> used(n, 0);
d[s] = 0;
for (int it = 0; it < n; it++) {
int v = -1;
for (int i = 0; i < n; i++) if (!used[i] && (v == -1 || d[i] < d[v])) v = i;
if (d[v] == INF) break;
used[v] = 1;
for (auto [u, w] : g[v]) d[u] = min(d[u], d[v] + w);
}
return d;
}set, очень узкая — вставка с сохранением порядка и взятие первого элемента. Есть структура, которая делает это чуть быстрее.1:19:11 Эта структура — priority_queue. Она умеет push и pop (добавить и достать первый элемент) (1:19:58–1:20:16). Одна особенность: очередь сортирует «в обратном порядке», сверху лежит наибольший элемент. Чтобы получить минимум, кладут расстояние с минусом или указывают компаратор greater (1:19:18–1:19:53).
1:20:16 Проблема. В set пара $(D,u)$ для вершины была одна, а в priority_queue вершину можно положить дважды — например, если её релаксировали две разные вершины $v_1,v_2$ (1:20:16–1:20:48). Лишнюю копию не хочется обрабатывать, поэтому при извлечении пары $(d,u)$ проверяем: если $d\ne D[u]$, то пара устарела — делаем continue (1:20:48–1:21:04).
// Дейкстра на priority_queue: дубликаты пропускаем проверкой d != d[v]
vector<ll> dijkstra_pq(int n, const vector<vector<pair<int,int>>>& g, int s) {
vector<ll> d(n, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> q; // минимум наверху
d[s] = 0; q.push({0, s});
while (!q.empty()) {
auto [dv, v] = q.top(); q.pop();
if (dv != d[v]) continue; // устаревшая копия
for (auto [u, w] : g[v])
if (d[u] > d[v] + w) { d[u] = d[v] + w; q.push({d[u], u}); }
}
return d;
}1:22:35 Асимптотика. Лектор выводит её в обсуждении с залом. В очереди может оказаться до $m$ записей, на каждую приходится вставка и извлечение за логарифм, итого $O(m\log m)$. Так как граф без петель и кратных рёбер, $m\le n^2$, поэтому $\log m\le 2\log n$ и обычно пишут просто $O(m\log n)$ (1:23:15–1:23:46). На практике это обычно быстрее, чем set (1:23:48–1:23:57).
1:24:32 Своя очередь на массиве. Обычная queue в C++ — надстройка над deque, поэтому иногда работает долговато. Если известно, что в очередь попадёт не больше $n$ элементов, заводим массив размера порядка $n+1$ и храним границы $[L,R)$ полуинтервала: добавление в конец — q[R++] = x, удаление из начала — L++ (1:24:40–1:25:27). Работает быстрее; нужно редко, но лектору пригодилось (1:25:27–1:25:48).
1:25:48 Задача для тех, кому скучно. В Дейкстре используется очередь с приоритетами; обычная куча — двоичная (у каждой вершины два сына). Можно ли сделать кучу, где у каждой вершины около $n$ детей? Лектор замечает: тогда вставка и удаление становятся дешёвыми для одного из действий, а в предельном случае получается ровно «тупой» поиск минимума за $n$ (1:25:57–1:26:48). Подробнее про кучу лектор обещает рассказать, когда речь дойдёт до декартова дерева (1:26:58–1:27:15).
1:27:25 Рёбра веса 0 и 1. Чтобы BFS работал, нужно только, чтобы очередь всегда была отсортирована: сначала «иксы», потом «иксы плюс один». Для этого вместо очереди берём дек: при релаксации по ребру веса $0$ вершину кладём в начало дека, по ребру веса $1$ — в конец. Инвариант сохраняется: слева всегда $x$, справа $x+1$ (1:27:35–1:28:21).
// 0-1 BFS на деке
vector<int> bfs01(int n, const vector<vector<pair<int,int>>>& g, int s) {
vector<int> d(n, INT_MAX);
deque<int> q; d[s] = 0; q.push_back(s);
while (!q.empty()) {
int v = q.front(); q.pop_front();
for (auto [u, w] : g[v])
if (d[u] > d[v] + w) {
d[u] = d[v] + w;
if (w == 0) q.push_front(u); else q.push_back(u);
}
}
return d;
}1:28:29 Ближайшая чёрная вершина. Граф, каждая вершина чёрная или белая; для каждой белой нужно найти расстояние до ближайшей чёрной. Два способа: (1) положить в очередь все чёрные вершины и запустить «мульти-BFS»; (2) завести фиктивную вершину, провести из неё рёбра длины $0$ во все чёрные и запустить BFS от неё. «По сути, это то же самое» — кому как понятнее (1:28:36–1:29:42).
1:29:50 Если веса рёбер — целые числа от $0$ до небольшого $K$, BFS тоже можно приспособить (если $K$ большое, запускают Дейкстру).
1:30:08 Способ 1. Разбить каждое ребро длины $x$ на $x$ рёбер длины один (с фиктивными вершинами) и запустить обычный BFS. Это работает плохо при большом $m$: вершин станет $n+\Theta(Km)$, и такой BFS работает за $O(n+Km)$ (1:30:08–1:30:53). «Иногда всё равно проходит».
1:30:56 Способ 2 (лектор сам его ни разу не писал: хватало лить рёбра). Заведём $K+1$ очередь — по аналогии с сортировкой подсчётом: первая очередь отвечает за расстояние $x$, вторая — за $x+1$, и т. д. до $x+K$ (1:31:07–1:31:36). Берём вершину из текущей очереди; релаксация по ребру длины $c$ кладёт вершину в очередь с номером $(D[v]+c)\bmod(K+1)$ — очереди зациклены (1:31:36–1:32:43). Помимо самих очередей храним номер той очереди, которую сейчас разбираем: пока в ней есть элементы, берём их, потом идём к следующей (1:32:52–1:33:21). Порядок «сначала $x$, потом $x+1$, …» мы поддерживаем вручную — «идея как в сортировке подсчётом» (1:33:21–1:33:42). Снова гарантируется, что мы всегда берём минимум, поэтому доказательство Дейкстры работает без изменений (1:33:42–1:33:53).
// BFS по весам 0..K на K+1 циклических очередях
vector<int> dial(int n, const vector<vector<pair<int,int>>>& g, int s, int K) {
vector<int> d(n, INT_MAX);
vector<queue<pair<int,int>>> q(K + 1); // в очереди (расстояние, вершина)
d[s] = 0; q[0].push({0, s});
int pending = 1; // сколько записей лежит в очередях
for (int cur = 0; pending > 0; cur = (cur + 1) % (K + 1)) {
while (!q[cur].empty()) {
auto [dv, v] = q[cur].front(); q[cur].pop(); pending--;
if (dv != d[v]) continue;
for (auto [u, w] : g[v])
if (d[u] > d[v] + w) {
d[u] = d[v] + w;
q[d[u] % (K + 1)].push({d[u], u}); pending++;
}
}
}
return d;
}priority_queue, их пропускаем проверкой dv != d[v]. Счётчик pending нужен, чтобы остановиться, когда все $K+1$ очередей пусты. Код проверен сравнением с обычной Дейкстрой на случайных графах.1:35:59 До сих пор мы считали расстояния из одной вершины и требовали неотрицательных рёбер. Иногда нужны расстояния между всеми парами вершин; запускать $n$ раз Дейкстру не оптимально — хочется переиспользовать информацию. «Динамику мы вам не просто так рассказывали» (1:36:07–1:36:42).
1:36:48 Простое $d[a][b]$ без дополнительного параметра не получается; нужен ещё один параметр. Пока в графе нет отрицательных рёбер (их «навернём за бесплатно» позже), кратчайший путь между $a$ и $b$ не повторяет вершин. Пусть $c$ — вершина пути с максимальным индексом (1:37:12–1:37:56). Определим $$dp_c[a][b]\;=\;\text{длина кратчайшего пути из }a\text{ в }b,\text{ все промежуточные вершины которого имеют индекс}\le c.$$
1:39:14 Порядок важен. Нельзя написать $dp[b][c]$ вместо $dp[c][b]$, если граф ориентированный: идём $a\to c\to b$ (1:39:23–1:39:43). Для Дейкстры и BFS ориентированность ничего не меняет (1:39:32–1:39:50). Перебор целиком — тройной цикл, время $O(n^3)$ (1:39:50–1:40:16).
1:40:09 Реализация. Внешний цикл по $c$ (в коде $k$), внутри перебираем $a$ и $b$, и $d[a][b]=\min(d[a][b],\,d[a][k]+d[k][b])$ (1:40:09–1:41:21). Слой хранить не нужно: между слоями $c-1$ и $c$ разница лишь в том, что на слое $c$ разрешена вершина $c$. Если мы «перетираем» слой на месте, ответ точно не станет хуже, а слои можно не хранить; и мы никак не конфликтуем с тем, что вершина $k$ может совпадать с $a$ или $b$ (1:41:21–1:42:07).
// Флойд: d[a][b] = min(d[a][b], d[a][k] + d[k][b]); k — внешний цикл
vector<vector<ll>> floyd(int n, const vector<vector<ll>>& w) {
auto d = w;
for (int k = 0; k < n; k++)
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
if (d[a][k] < INF && d[k][b] < INF) d[a][b] = min(d[a][b], d[a][k] + d[k][b]);
return d;
}1:42:07 База. Нужно быть аккуратным с петлями: $d[a][a]$ равно нулю либо длине петли (если она отрицательна). Положительная петля не нужна (1:42:07–1:42:54). Если петля отрицательная — расстояние равно $-\infty$.
1:43:03 Обычно нужно знать, до каких вершин можно «набрать как угодно маленькое значение»: из стартовой вершины $S$ можно попасть в отрицательный цикл, а из него — в вершину $T$ (1:43:10–1:43:50). Значит, нужно уметь находить вершины на отрицательных циклах и проверять достижимость $S\to x\to T$ (1:43:50–1:44:08).
1:44:15 Рассмотрим простой отрицательный цикл через вершину $x$. В какой-то момент Флойд пересчитывает $d[x][x]$ через промежуточную вершину $u$: $d[x][u]+d[u][x]$, и это в сумме даёт число меньше нуля. Поэтому вершины с $d[x][x]<0$ лежат на отрицательном цикле (1:44:27–1:45:17).
d[a][b] = max(NINF, min(d[a][b], d[a][k] + d[k][b])) (1:46:08–1:46:16).const ll INF = LLONG_MAX / 4, NINF = -INF;
// Флойд с отрицательными циклами: значения не опускаются ниже NINF
for (int k = 0; k < n; k++)
for (int a = 0; a < n; a++)
for (int b = 0; b < n; b++)
if (d[a][k] < INF && d[k][b] < INF)
d[a][b] = max(NINF, min(d[a][b], d[a][k] + d[k][b]));
// расстояние s -> t равно -бесконечности, если есть x:
// d[s][x] < INF, d[x][x] < 0, d[x][t] < INF1:46:16 Лектор советует сдать в контесте задачи на отрицательные циклы обоими способами — Фордом–Беллманом и Флойдом, — чтобы потренироваться (1:46:16–1:46:27). На вопрос из зала, будут ли потоки, лектор отвечает, что будут; а динамика такого рода «встречается много где, потому что это очень лёгкий способ считать динамику» (1:46:35–1:46:59). Дальше — перерыв (1:47:06).
2:48:25 Вторую часть читает другой лектор. Он напоминает, что первый лектор рассказал Флойда, и переходит к алгоритму Форда–Беллмана (2:48:40–2:49:10).
2:49:23 В чём уникальность BFS. В BFS мы знаем, в каком порядке нужно перебирать рёбра, чтобы обновлять расстояния. Усложним задачу: пусть у рёбер произвольные веса, не обязательно положительные — порядок рёбер нам теперь неизвестен (2:49:30–2:50:06). Дейкстра при отрицательных рёбрах не работает; её можно «починить», но для этого потребуется тот же Форд–Беллман (2:50:09–2:50:34).
2:50:42 Идея. Возьмём какую-нибудь перестановку рёбер и повторим её $m$ раз подряд; получится последовательность длиной $m^2$ (2:50:42–2:51:13). Тогда любой рёберно-простой путь встречается в ней как подпоследовательность: первое ребро пути берём из первой копии перестановки, второе — из второй и т. д. (2:51:19–2:51:36). Значит, если проходить рёбра в таком порядке и обновлять расстояние вдоль каждого, мы обязательно «поймаем» нужный порядок рёбер для любого кратчайшего пути. Более того, перестановка между блоками может быть другой — важно лишь, чтобы в каждом блоке были все рёбра (2:51:41–2:52:03).
2:52:38 Предположим, что отрицательных циклов нет. Тогда любой кратчайший путь содержит не более $n$ вершин: цикл неотрицательной длины можно выбросить, не увеличив расстояние (2:52:45–2:53:01). Поэтому достаточно $n$ блоков: $n$ раз пройти по всем рёбрам в любом порядке и вдоль каждого ребра $(u,v)$ сделать $d[v]=\min(d[v],\,d[u]+w)$ (2:53:01–2:53:16).
2:55:12 Время. Сначала лектор оценивает наивно как $nm^2$, но тут же замечает, что мы не проходим всю длинную последовательность целиком, а делаем $n$ проходов по $m$ рёбрам, то есть $$O(nm).$$ (2:55:35–2:56:14).
// Форд–Беллман: n-1 проходов по всем рёбрам; возвращает true, если достижимый из s отрицательный цикл
bool ford(int n, const vector<E>& e, int s, vector<ll>& d) {
d.assign(n, INF); d[s] = 0;
for (int it = 0; it < n; it++) {
bool ch = false;
for (auto& x : e)
if (d[x.a] < INF && d[x.b] > d[x.a] + x.w) { d[x.b] = d[x.a] + x.w; ch = true; }
if (!ch) return false; // ничего не изменилось — дальше тоже не изменится
if (it == n - 1) return true; // изменение на n-м проходе: есть отрицательный цикл
}
return false;
}2:57:08 Лектор отмечает, что алгоритм хорош для разреженных графов ($m$ порядка $n$, а не $n^2$): тогда его время около $n^2$ (2:57:08–2:58:00).
// Форд–Беллман на очереди (без отрицательных циклов)
vector<ll> spfa(int n, const vector<vector<pair<int,ll>>>& g, int s) {
vector<ll> d(n, INF); vector<char> in(n, 0); queue<int> q;
d[s] = 0; q.push(s); in[s] = 1;
while (!q.empty()) {
int v = q.front(); q.pop(); in[v] = 0;
for (auto [u, w] : g[v])
if (d[u] > d[v] + w) { d[u] = d[v] + w; if (!in[u]) { in[u] = 1; q.push(u); } }
}
return d;
}3:04:52 Как искать цикл отрицательного веса с помощью Форда–Беллмана? Гораздо проще, чем кажется: если мы сделали больше $n$ итераций, цикл есть, если меньше — нет (3:04:52–3:05:07). Цикл по итерациям продолжается, пока что-то обновляется, то есть пока есть кратчайший путь строго такой длины; а отрицательный цикл существует тогда и только тогда, когда есть «кратчайший путь любой длины, сколь угодно большой» (3:05:12–3:05:44).
3:05:44 Как найти сам цикл. Нужно хранить массив предков — откуда обновилось минимальное расстояние — и найти цикл в нём (3:05:44–3:06:04).
3:06:22 Задача. В ориентированном графе найти цикл, у которого средний вес ребра (сумма весов, делённая на число рёбер) как можно меньше (3:06:28–3:08:38). Перебирать циклы бесполезно: их может быть очень много. Лектор приводит пример графа из цепочки пар вершин, где можно выбрать любое подмножество пар и «наворачивать крюк» (3:07:01–3:08:00).
3:08:47 Идея. Минимум искать напрямую мы не умеем, но умеем проверять, что минимум меньше нуля — то есть есть отрицательный цикл (3:08:47–3:08:58). Поэтому делаем бинарный поиск по ответу: вычитаем кандидата из веса каждого ребра. Средний вес любого цикла уменьшается ровно на это число (3:09:01–3:09:16). Теперь проверяем, появился ли цикл отрицательного веса: если минимальный средний вес меньше кандидата, то после вычитания отрицательный цикл гарантированно есть; если больше — отрицательных циклов нет (3:10:25–3:10:59). Общая идея: если вы умеете проверять «минимум меньше $K$» для фиксированного $K$, то $K$ можно «подвинуть» вычитанием из всех рёбер (3:10:59–3:12:09).
3:09:40 Проверка отрицательного цикла — Флойдом или Фордом–Беллманом; суммарно получается $\log C\cdot n^3$ (3:09:40–3:09:49).
// Флойд на double: есть ли цикл отрицательного веса (d[x][x] < 0)
bool has_neg(int n, vector<vector<double>> d) {
for (int k = 0; k < n; k++) for (int a = 0; a < n; a++) for (int b = 0; b < n; b++)
d[a][b] = min(d[a][b], d[a][k] + d[k][b]);
for (int i = 0; i < n; i++) if (d[i][i] < -1e-12) return true;
return false;
}double min_mean(int n, const vector<vector<double>>& w, double lo, double hi) {
for (int it = 0; it < 60; it++) {
double mid = (lo + hi) / 2;
auto d = w;
for (auto& r : d) for (auto& x : r) x -= mid; // вычитаем кандидата из всех рёбер
if (has_neg(n, d)) hi = mid; else lo = mid;
}
return lo;
}lo и hi нужно выбирать так, чтобы ответ лежал между ними, например от минимального до максимального веса ребра.3:12:12 Цикл минимального веса. Если рёбра неотрицательные, то после Флойда минимальный цикл ищем как минимум по парам вершин $x\ne y$ суммы $d[x][y]+d[y][x]$: так в цикле заведомо хотя бы две вершины и он нетривиален (3:12:17–3:13:35). Отрицательный случай тривиален — расстояние равно $-\infty$.
3:14:37 Последняя задача — на неявный граф. Обычно граф задан матрицей или списками смежности, а здесь он задан так: из вершины $u$ есть ребро весом $w$ во все вершины с индексами от $l$ до $r$. Рёбер получается очень много, но их можно описать отрезками (3:14:49–3:15:42). Нужно найти расстояния от одной вершины до всех. Лектор отмечает: любая задача решается за квадрат, но мы хотим быстрее, примерно за $(n+m)\log n$ (3:15:42–3:16:00, 3:20:17–3:20:27).
3:16:34 В Дейкстре с set проблемы с самим множеством нет, проблема в том, чтобы быстро перебрать рёбра (3:16:40–3:17:33). Лектор обсуждает с залом несколько идей — перебирать рёбра в порядке уменьшения расстояния, хранить для отрезков веса, искать на отрезке «все, которые можно уменьшить» (3:17:40–3:20:58) — и приходит к такой схеме.
3:21:14 Дерево отрезков вместо множества. Храним в дереве отрезков в точке $v$ текущее расстояние до $v$ (3:21:14–3:21:37). Раз расстояние и так хранится в дереве, доставать минимум можно не из множества, а из корня дерева (3:24:00–3:24:17). Релаксация по ребру $u\to[l,r]$ с весом $w$ — это операция «$\min=\,D[u]+w$ на отрезке $[l,r]$» (3:24:17–3:24:31). Лектор замечает, что обычное дерево отрезков с массовой операцией — сложная структура, а у нас частный случай: нужно лишь получать минимум (3:24:31–3:25:02).
3:25:02 В вершине дерева хранится текущий минимум и модификатор (как в массовых операциях). Пусть мы пришли в вершину с операцией «$\min=x$» (3:25:02–3:25:10). Лектор разбирает два случая:
mn = min(mn, x) и tag = min(tag, x), а модификатор при спуске применяется к обоим детям. Тогда каждая листовая вершина отрезка действительно получит значение $\min(D,x)$, а не только та, в которой «лежит» минимум.3:27:04 Как не доставать одну вершину дважды. Когда вершина вынута из дерева, её нужно «выбросить». Лектор предлагает: при взятии минимума спуститься к листу и записать в него специальный флаг («$-1$»), который при подсчёте минимума игнорируется — для вершины-флага минимум считается нейтральным, как $+\infty$, но флаг не перезатирается операциями «$\min=$» (3:27:04–3:28:35). В общем случае так можно игнорировать не одно число, а любое условие (3:28:35–3:28:46).
3:28:46 Время. Каждое ребро-отрезок — одна массовая операция $O(\log n)$, а каждая вершина вынимается один раз и «закрывается» за $O(\log n)$; минимум из корня достаётся за $O(1)$. Получаем $$O\bigl((n+m)\log n\bigr)$$ (3:28:46–3:29:17).
// Дерево отрезков для неявной Дейкстры: chmin на отрезке и вынимание минимума
struct Seg {
static constexpr ll DEAD = LLONG_MAX; // метка «вершина уже вынута»
int n; vector<ll> mn, tg;
Seg(int n) : n(n), mn(4 * n, INF), tg(4 * n, INF) {}
void app(int v, ll x) { if (mn[v] != DEAD) { mn[v] = min(mn[v], x); tg[v] = min(tg[v], x); } }
void push(int v) { if (tg[v] < INF) { app(2*v, tg[v]); app(2*v+1, tg[v]); tg[v] = INF; } }
void chmin(int v, int l, int r, int a, int b, ll x) {
if (b < l || r < a) return;
if (a <= l && r <= b) { app(v, x); return; }
push(v); int m = (l + r) / 2;
chmin(2*v, l, m, a, b, x); chmin(2*v+1, m+1, r, a, b, x);
mn[v] = min(mn[2*v], mn[2*v+1]);
}
int take(int v, int l, int r) { // вынуть вершину с минимальным d, пометить её DEAD
if (l == r) { mn[v] = DEAD; return l; }
push(v); int m = (l + r) / 2, res;
if (mn[2*v] <= mn[2*v+1]) res = take(2*v, l, m); else res = take(2*v+1, m+1, r);
mn[v] = min(mn[2*v], mn[2*v+1]);
return res;
}
};// ребро-отрезок: из вершины во все вершины l..r с весом w
struct SE { int l, r; ll w; };// Дейкстра по неявному графу
vector<ll> dijkstra_implicit(int n, const vector<vector<SE>>& g, int s) {
Seg t(n); vector<ll> d(n, INF);
t.chmin(1, 0, n - 1, s, s, 0);
for (int it = 0; it < n; it++) {
if (t.mn[1] >= INF) break; // осталось только недостижимое
ll dv = t.mn[1];
int v = t.take(1, 0, n - 1);
d[v] = dv;
for (auto& e : g[v]) t.chmin(1, 0, n - 1, e.l, e.r, dv + e.w);
}
return d;
}DEAD (в коде это наибольшее возможное значение, чтобы метка не побеждала при взятии минимума и не перезатиралась операцией chmin), а недостижимая пока вершина хранит обычное «бесконечное» расстояние. Реализация проверена сравнением с Дейкстрой по явно развёрнутым рёбрам на 3000 случайных графов.3:30:11 Лекция закончилась; лекторы остались отвечать на вопросы, пока участники решали контест. Вот вопросы, относящиеся к материалу.
4:42:31 Как ускорить «количество меньших на отрезке» в дереве с отсортированными списками (merge sort tree). Обычно запрос разбивают на $O(\log n)$ отрезков и в каждом делают бинарный поиск — это $O(\log^2 n)$ (4:42:48–4:43:10). Чтобы получить $O(\log n)$, во время построения при слиянии списков детей для каждой позиции запоминаем, где стояли указатели в левом и правом ребёнке. Тогда достаточно одного бинарного поиска в корне, а в детях позиция берётся готовым указателем (4:43:10–4:43:57). Это называется каскадированием; на практике это «суперрабочая» оптимизация (4:44:04–4:44:34).
4:44:41 Про память. Хранить vector внутри каждой вершины плохо: динамические массивы лежат в памяти как попало. Лучше один большой массив, а в вершине — левый и правый указатель на её кусок; слияние тогда пишет результат в позицию $[L_C,R_C)$ (4:44:54–4:46:19). Обновления такая структура не выдерживает (все указатели сдвигаются) (4:46:22–4:46:47).
4:47:03 Множество, в котором вставок сильно больше, чем запросов lower_bound. Тогда его выгодно сделать корневой декомпозицией: один счётный массив и для каждого блока длины порядка $\sqrt{n}$ — количество элементов. lower_bound и порядковая статистика идут сначала по блокам, потом внутри блока — $O(\sqrt{n})$; а обновление — $O(1)$: мы меняем одну ячейку и счётчик блока (4:47:11–4:47:49).
4:47:49 Дальше в курсе будет алгоритм «корневой по запросам» — отрезки группируют по блоку, в котором лежит левая граница (алгоритм Мо) (4:47:55–4:48:51). На этом занятие заканчивается.