0:00 Занятие начинается с разбора контеста по потокам. Лектор разбирает почти все задачи по порядку и повторяет главную мысль: если в задаче есть двудольный граф, стоит искать в ней поток; если нужно минимизировать штрафы — разрез. Условия задач приводятся так, как их пересказал лектор.
0:00 Нужно найти поток размера два. Допустим, он найден; его декомпозиция даёт пути: находим любой путь из $1$ в $N$ по рёбрам с потоком и записываем его в ответ (0:09–0:22). Затем уменьшаем поток вдоль этого пути на единицу и повторяем ещё раз (0:26–0:35). Могут остаться лишние рёбра, которыми мы не воспользовались, — но это только циклы, их всегда можно выбросить, величина потока от этого не меняется (0:44–1:00).
1:00 На клетчатом поле написаны символы H, O, N, C с валентностями $1,2,3,4$. Нужно проверить, можно ли провести рёбра между соседними клетками (между двумя клетками — не более одного ребра) так, чтобы степень каждой клетки равнялась её валентности (1:09–2:00).
2:00 Клетки шахматно раскрашены, поэтому поле — двудольный граф (2:09–2:24). Строим сеть: из источника в клетку левой доли идёт ребро с пропускной способностью, равной валентности; из клетки правой доли в сток — тоже по валентности; между соседними клетками — ребро ёмкости $1$ (2:32–3:31). Находим максимальный поток: рёбра в середине, по которым идёт поток, и есть выбранные связи. Условие выполнено, когда все рёбра из источника и в сток насыщены, то есть сумма валентностей левой доли равна сумме валентностей правой и равна величине потока (3:41–4:41). «Если вы видите двудольный граф, скорее всего, должна выйти какая-нибудь сеть» (4:41–4:49).
4:57 Картинка из клеток двух цветов. Между любыми соседними клетками разного цвета обязательно проводится серая линия стоимостью $g$. Кроме того, чёрную клетку можно перекрасить в белую за одну цену, а белую в чёрную — за другую (5:06–5:39).
5:39 Задача на минимизацию, поэтому «потоком думать не очень хорошо» — нужно думать про минимальный разрез (5:39–6:09). Пусть итоговый чёрный цвет клетки означает, что она лежит в $S$-части разреза, итоговый белый — в $T$-части (6:19–6:48).
8:07 Максимальный поток в этой сети и есть ответ. Если нужно ещё и восстановить итоговую картинку, достаточно взять разбиение на $S$ и $T$, которое получается автоматически после алгоритма Форда–Фалкерсона: по минимальному разрезу и красится вся картинка (8:17–9:07).
9:14 Здесь наконец-то просят написать максимальный поток. В предыдущих задачах Форда–Фалкерсона хватало: в первой поток равен двум, во второй поток не превосходит порядка $NM/4$, в третьей сеть не очень большая. В этой сеть большая, тестов много — нужно было честно писать алгоритм Диница (9:23–10:04).
10:04 Есть $n$ человек и $m$ видов чая; чая $i$-го вида $a_i$ пакетиков; у каждого человека есть набор любимых сортов. Нужно найти максимальное число дней, в каждый из которых каждый пьёт по кружке только любимого чая (10:15–10:40).
10:40 Бинарный поиск по ответу $T$: можно ли прожить $T$ дней? Для проверки строим двудольную сеть: слева виды чая, справа люди. От источника к чаю $i$ — ребро ёмкости $a_i$; от чая к человеку, который его любит, — ребро ёмкости $\infty$ (любимый чай можно пить сколько угодно раз); от человека к стоку — ребро ёмкости $T$, ведь каждый должен выпить ровно $T$ кружек (10:53–11:58). Поток разлагается на пути, и каждая проверка — отдельное условие: чая выпито не больше, чем есть; человек пьёт только любимый; человек не выпил слишком много (12:12–12:30). Максимально возможный поток равен $T\cdot n$: если он достигается, все выпили по кружке чая во все $T$ дней, иначе — нельзя (12:39–13:17).
13:25 Здесь пропускные способности до $10^9$. Сначала находим максимальный поток, потом раскладываем его на пути: находим путь из $S$ в $T$ по рёбрам с положительным потоком, смотрим, какой максимальный поток можно по нему пустить (минимум по ребру), выделяем этот путь с таким весом и вычитаем его из потока. В ходе процесса получается декомпозиция (13:31–14:25). Минимизировать число путей не требуется, а слишком много их не получится — «надо было просто поверить, что будет немного; это учебная задача на алгоритм» (14:25–14:51).
14:58 Есть темы; между ними есть зависимости (ориентированный граф, возможны циклы), у каждой темы своя полезность $x_i$ — положительная или отрицательная. Нужно выбрать множество тем $S$, замкнутое по зависимостям (оно не зависит ни от чего вне себя), с максимальной суммарной полезностью $\sum_{i\in S}x_i$ (14:58–16:05).
16:18 С точки зрения потока здесь трудно придумать смысл — стоимости не прикрутить, — поэтому идём через минимальный разрез. Тема в $S$-части означает «рассказали», в $T$-части — «не рассказали» (16:34–17:05). Задачу максимизации превращаем в минимизацию штрафов, причём пропускные способности должны быть неотрицательными (17:09–17:45):
21:39 Лектор разбирает пример: у трёх тем полезности $1$, $-2$, $3$ без зависимостей поток равен нулю — мы получаем бонус за темы $1$ и $3$, а тему $-2$ рассказывать не обязаны. Если бы вместо этого было $-1$ и $3$ с зависимостью второй темы от первой, поток был бы равен единице: рассказываем две темы, но «платим» одну единицу (21:39–23:15). Ещё раз лектор подчёркивает: об этом нельзя думать «с точки зрения потока» — вершины покрашены в два цвета, и вы просто накидываете штрафы (23:15–23:32).
23:32 Это задача регионального этапа 2019–2020 годов; лектор замечает, что с тех пор на региональных потоков не было (на комбинаторику — были) (23:32–23:50). Даны $N$ массивов $a^{(1)},\dots,a^{(N)}$ длины $k$ ($N$ чётно). Два массива $a$ и $a'$ могут образовать пару, если для некоторого общего массива $b$ в каждой позиции $i$ либо $a_i\le b_i\le a'_i$, либо $a_i\ge b_i\ge a'_i$ — то есть $b_i$ лежит между значениями пары. Дополнительное условие: первые элементы всех массивов различны (23:57–25:17).
25:36 Шаг 1: как выглядит $b$. По каждой координате $b_i$ должно быть медианой: между двумя центральными значениями этой координаты. Тогда массивы по координате делятся на «меньше медианы» и «больше медианы»; если два центральных значения совпали, то остаётся ещё и «равные медиане» (25:36–27:57).
28:00 Шаг 2: сжатие координат. Каждый массив превращается в вектор из $\{-1,0,+1\}$ той же длины ($-1$ — меньше, $+1$ — больше, $0$ — равные медиане). Два массива образуют пару, если по каждой координате их символы не равны ненулевому одному и тому же значению, то есть $c_i\cdot c'_i\le0$ для всех $i$ (29:35–30:05). Первая координата никогда не $0$, поэтому граф двудольный: слева — те, у кого на первой позиции $-1$, справа — те, у кого $+1$ (30:05–30:30).
31:39 Массивов может быть до $200\,000$, и искать паросочетание «в лоб» медленно. Но после сжатия различных векторов немного — не больше $3^k$ (длину сжатого вектора лектор называет порядка семи) (31:42–32:17). Одинаковые векторы склеиваем в одну вершину сети: ребро из источника к вершине-классу имеет ёмкость, равную числу массивов этого класса; рёбра в середине ведут только слева направо и имеют ёмкость $\infty$ (32:24–33:38). Для восстановления ответа запоминаем номер каждого ребра, а затем по найденному потоку жадно раздаём пары: для каждой пары классов берём нужное число индексов из списков индексов этих классов (33:38–34:46).
35:16 Есть четыре центра. Партии роботов (их $t$ штук, $t\le100$) приходят по очереди; $i$-я партия содержит $n_i$ роботов и может расположиться в любых клетках квадрата вокруг центра номер $b_i$ радиуса $r_i$ (мобильность); в одной клетке — не более $Q$ роботов. Нужно найти максимальное число роботов, которых можно разместить по порядку прихода: номер первой партии, которую нельзя разместить целиком, и сколько из неё удастся добавить (35:16–37:55).
37:55 Исходная сеть. Источник → партия с ёмкостью $n_i$; партия → клетка своего квадрата с ёмкостью $\infty$; клетка → сток с ёмкостью $Q$ (38:07–39:13). Если нужно проверить, можно ли разместить всех, достаточно найти максимальный поток. Но добавлять роботов по одному слишком долго.
39:48 Бинарный поиск по префиксу партий. Сначала всех партий помещается столько-то, потом уже нет, поэтому ищем бинарным поиском первый префикс, который нельзя разместить целиком (39:48–40:27). Пусть максимальный поток для такого префикса равен $F$, а первые $i$ партий (префикс до неё) размещены. Тогда ответ: $i$ партий целиком, плюс из следующей партии можно добавить ещё $F-\sum_{j\le i}n_j$ роботов (40:27–41:07).
41:07 Почему это верно. Лектор отмечает, что рассуждение не разбиралось на лекции, но оно полезное. Вдруг в максимальном потоке «насыщена» не первая, а более ранняя партия? Доказательство: пусть уже есть поток, насытивший первые $i$ партий. По теореме Форда–Фалкерсона его можно достроить до максимального увеличивающими путями. Такой путь начинается в $S$ и идёт в $(i+1)$-ю партию (остальные рёбра из $S$ насыщены) и гуляет по сети до $T$. Если бы он «отменял» поток по ребру из $S$ в уже насыщенную партию, то зашёл бы в $S$ второй раз, то есть путь не простой; но если в остаточной сети есть какой-то путь из $S$ в $T$, то есть и простой. Значит, можно всегда выбирать такие пути, которые не отменяют поток по рёбрам первых $i$ партий (41:07–45:08). Такой приём позволяет сильно упрощать задачу — не надо бинарить ещё и число роботов во второй партии (42:19–42:45). Итого — около восьми итераций бинпоиска, на каждой запускается максимальный поток (45:44–46:28).
46:28 Вторая проблема: сеть огромна. Прямоугольник — $10^5\times10^5$ клеток. Клетки можно объединить по областям: если две клетки входят в один и тот же набор квадратов, они эквивалентны и склеиваются в одну клетку с ёмкостью $Q\cdot(\text{их число})$ (46:34–47:24). Но областей в худшем случае порядка $t^2$ (квадраты двух центров образуют сетку из $2t$ вертикальных и $2t$ горизонтальных линий), а рёбер $t^3$: порядка $10^4$ вершин и $10^6$ рёбер, умножить на восемь запусков — слишком медленно даже для Диница (47:32–49:24).
49:24 Решение через минимальный разрез. Не ищем сам поток, а считаем разрез напрямую по теореме Форда–Фалкерсона (49:35–49:50). Выберем множество партий $B$ в $S$-части. Тогда разрезаются рёбра из $S$ в партии, не вошедшие в $B$ (штраф $n_j$), и бесконечные рёбра обязывают отправить в $S$ все клетки квадратов из $B$, а за каждую такую клетку платим $Q$ (ребро клетка → сток) (50:10–52:29): $$\text{разрез}(B)=\sum_{j\notin B}n_j+Q\cdot\bigl|\textstyle\bigcup_{j\in B}\mathrm{square}_j\bigr|\;\to\;\min.$$
53:06 Так как центров всего четыре, квадраты вокруг одного центра вложены друг в друга: если мы взяли большой квадрат, все меньшие даются бесплатно. Поэтому для каждого центра достаточно перебрать, сколько «наименьших» квадратов входит в $B$. Вариантов $(t_1+1)(t_2+1)(t_3+1)(t_4+1)$, где $t_c$ — число партий с центром $c$. По неравенству о средних это не больше $\bigl(\frac{t_1+\dots+t_4+4}{4}\bigr)^4=26^4<500\,000$, а бинпоиск делает восемь итераций (53:41–55:05).
55:05 Первая часть разреза (сумма $n_j$ невошедших) считается через предварительную сортировку и суммы. Сложнее вторая: площадь объединения четырёх квадратов (по одному, самому большому, на центр) (55:13–55:47). Её удобно считать формулой включений-исключений: пересечение прямоугольников — снова прямоугольник, а пересекать проще, чем объединять (55:47–56:44). Для всех $16$ подмножеств координаты пересечения считаются минимумами и максимумами границ, что можно получить копированием массива с $\min=$ (57:07–58:06). В авторском решении просто перебирали все подмножества — это тоже быстро работало (58:42–58:49).
ll union_area(const vector<Rect>& r) {
int k = r.size(); ll res = 0;
for (int mask = 1; mask < (1 << k); mask++) {
ll x1 = LLONG_MIN, y1 = LLONG_MIN, x2 = LLONG_MAX, y2 = LLONG_MAX;
for (int i = 0; i < k; i++) if (mask >> i & 1) { x1 = max(x1, r[i].x1); y1 = max(y1, r[i].y1); x2 = min(x2, r[i].x2); y2 = min(y2, r[i].y2); }
ll area = max(0LL, x2 - x1) * max(0LL, y2 - y1);
res += (__builtin_popcount(mask) % 2 ? 1 : -1) * area;
}
return res;
}59:11 Клеточное поле — двудольный граф (шахматная раскраска); нужно найти максимальное независимое множество клеток. Как искать независимое множество в двудольном графе, разбиралось на лекции: через паросочетание. Задача делается быстро (59:11–59:38).
59:47 Лектор отдельно упоминает класс графов, где потоки можно искать быстро (59:55–1:00:03). Задача звучит так, будто её можно решить конструктивно, но за 2–3 года никто конструктива не придумал (1:00:12–1:00:25). Нужно расставить все $n$-битные числа ровно с $n/2$ единицами в перестановку так, чтобы $i$-е число и $i$-е число этой перестановки различались ровно в $k$ битах (1:00:25–1:02:32).
1:02:40 Строим двудольный граф: слева все такие числа, справа те же числа, ребро проводим, если числа различаются ровно в $k$ позициях. Вершин в каждой доле $\binom{n}{n/2}\le\binom{20}{10}\approx2\cdot10^5$, а степень каждой вершины одинакова и равна $\binom{n/2}{k/2}^2$ (нужно выбрать $k/2$ нулей и $k/2$ единиц для переворота) (1:02:48–1:03:53). Граф слишком «жирный», чтобы его построить; но он регулярный, а в регулярном двудольном графе паросочетание ищется за $O(n\log n)$ (где $n$ — число вершин) (1:04:16–1:04:32).
1:04:32 Идея: это алгоритм Куна, но увеличивающую цепочку ищем не поиском в глубину, а случайным блужданием. Берём свободную вершину слева, переходим в случайного соседа справа; если он свободен — цепочка найдена; иначе идём в его пару слева и снова в случайного соседа справа, и так далее. Посещённые вершины запоминать не нужно — второй раз прийти можно и нужно, потому что ребро теперь выберется другое (1:04:40–1:05:57). Для регулярных графов всегда существует совершенное паросочетание, а такой процесс работает за $O(n\log n)$ (1:05:30–1:05:57). Лектор обещает выложить в канале доказательство (комбинаторное по индукции; можно и линейной алгеброй или теорией вероятностей) (1:05:57–1:06:20).
1:06:20 Полученный путь может быть не простым; из него за линейное от длины время получается простой, по которому и увеличиваем паросочетание (1:06:42–1:06:57). Рёбра хранить вообще не нужно: достаточно уметь выбирать случайное исходящее ребро — случайные $k/2$ нулей и $k/2$ единиц (1:07:26–1:07:41). Лектор советует попробовать реализовать это — тема редкая, но «стрёмно может выстрелить» (1:07:06–1:07:26).
1:07:49 Даны $n\le500$ условий вида «на позициях $l..r$ в какой-то из выписанных строк стоит данная подстрока»; нужно построить минимальное число строк, удовлетворяющих всем условиям (1:07:49–1:08:39).
1:13:42 Разбиение DAG на минимальное число путей — задача о максимальном паросочетании: каждую вершину раздваиваем на левую и правую копии, ребро $i\to j$ превращаем в ребро между левой копией $i$ и правой копией $j$. Паросочетание максимального размера — максимальное множество рёбер, у которого в каждую вершину входит и из неё выходит не более одного ребра, то есть набор цепочек; чем больше рёбер, тем меньше путей, ведь «число рёбер плюс число путей» равно числу вершин $N$ (1:13:42–1:14:53). Для каждой цепочки строим строку: берём строку из букв «A» и по всем условиям цепочки расставляем символы (1:15:07–1:15:26). Такие множества называют частично упорядоченными: для интереса можно почитать (1:14:59–1:15:07).
1:15:55 Эта задача ближе к тому, что лектор рассказывал о разрезах; она относительно свежая, решили её немногие, поэтому была выбрана как интересная (1:15:55–1:16:24). Есть две группы гусениц на прямой: у группы — число $c_i$, координата $x_i$ и кругозор $y_i$ (отрезок $[x_i-y_i,\ x_i+y_i]$). Нужно проверить, что каждой гусенице первого типа можно найти пару второго типа с непересекающимся отрезком кругозора (1:17:37–1:19:16).
1:19:16 Групп до $300\,000$, рёбер ещё больше, поэтому ни Кун, ни обычный поток не подходят (1:19:24–1:19:54). Используем теорему Форда–Фалкерсона: максимальный поток должен равняться $\sum c$ по первому типу, значит, надо смотреть на минимальный разрез (1:19:54–1:20:46). Удобнее перейти к условию Холла: для любого множества групп первого типа число гусениц второго типа, с которыми они могут быть в паре, не меньше числа самих гусениц (1:25:32–1:26:37).
1:30:08 Рассмотрим множество групп первого типа. Группа второго типа «видима» этому множеству, если её отрезок не пересекается хотя бы с одним отрезком из множества: либо её левая граница $\ge$ правой границы какого-то отрезка (то есть $\ge\min R$), либо правая граница $\le$ левой границы какого-то отрезка (то есть $\le\max L$) (1:30:15–1:31:23). Значит, от множества интересуют только минимальная правая граница $R$ и максимальная левая граница $L$; а при проверке условия Холла выгодно докидывать в множество все группы, отрезок которых содержит $[L,R]$ (1:31:23–1:33:23).
1:40:22 Фиксируем $R$ и перебираем $L$. Мужские группы, которые можно докинуть в множество, — те, у которых правая граница $\ge R$ и левая граница $\le L$: каждая такая группа прибавляет своё число $c$ на суффиксе значений $L$ (1:41:09–1:43:34). Женские группы учитываются отдельно, чтобы никого не посчитать дважды: те, у которых левая граница больше $R$, добавляются к ответу как константа; остальные, у которых правая граница не больше $L$, вычитаются на суффиксе (1:43:53–1:44:56). В итоге для каждого $L$ получается «баланс», и нужно проверить, что он нигде не положителен. Если двигать $R$ справа налево, всё сводится к операциям «прибавление на отрезке» и «минимум на отрезке» — это дерево отрезков (1:45:04–1:45:23). Некоторые значения $L$ запрещены (для них нет подходящей группы) — туда прибавляют бесконечность, чтобы их не учитывать в минимуме (1:38:18–1:39:22).
1:45:23 Итог разбора: много задач сводятся к «подумать над минимальным разрезом»; никто почти не решал последние, но они не слишком сложные — просто надо «подолбиться с разрезами» (1:45:26–1:45:47). Затем слово получает второй лектор (1:45:47–1:45:56).
1:45:56 Лекцию читает второй лектор. Она построена как серия коротких задач, в каждой из которых нужна та или иная корневая идея: разбить объекты на «большие» и «маленькие», разбить массив или запросы на блоки, подобрать параметр $K$. Ниже порядок тот же, что и на лекции.
1:46:05 Задача. Дан граф с $n$ вершинами и $m$ рёбрами; в вершинах записаны числа. Запросы двух видов: прибавить число $x$ ко всем соседям вершины $v$; узнать число в вершине $v$ (1:46:05–1:47:18).
1:47:21 Идея. Разобьём вершины на лёгкие (степень меньше $K$) и тяжёлые (степень не меньше $K$) (1:47:21–1:47:43).
1:49:36 Время. Тяжёлых вершин не больше $2m/K$, потому что сумма всех степеней равна $2m$. Прибавление работает за $O(K)$ для лёгкой вершины и $O(1)$ для тяжёлой, узнавание — за $O(m/K)$. Оптимально взять $K=\sqrt m$: все операции за $O(\sqrt m)$ (1:49:44–1:50:35).
struct HeavyLight {
int n, K;
vector<vector<int>> g, heavyNb; // heavyNb[v] — тяжёлые соседи v
vector<ll> a, lazy; // lazy[h] — сколько прибавили всем соседям тяжёлой вершины h
vector<char> heavy;
HeavyLight(int n, const vector<pair<int,int>>& edges, int K) : n(n), K(K), g(n), heavyNb(n), a(n, 0), lazy(n, 0), heavy(n, 0) {
for (auto [u, v] : edges) { g[u].push_back(v); g[v].push_back(u); }
for (int v = 0; v < n; v++) heavy[v] = (int)g[v].size() >= K;
for (int v = 0; v < n; v++) for (int u : g[v]) if (heavy[u]) heavyNb[v].push_back(u);
}
void add(int v, ll x) { // прибавить x всем соседям v
if (!heavy[v]) { for (int u : g[v]) a[u] += x; } // лёгкая: deg < K
else lazy[v] += x; // тяжёлая: откладываем
}
ll get(int v) { // не более 2m/K тяжёлых соседей
ll r = a[v];
for (int h : heavyNb[v]) r += lazy[h];
return r;
}
};1:51:19 Задача. Есть предметы весов $w_i$, суммарный вес $W$. Две версии: (а) узнать все суммы, которые можно набрать подмножеством предметов; (б) узнать минимальное число предметов, которыми можно набрать данную сумму. Обе нужно решить за $O(W\sqrt W)$ (1:51:19–1:52:45).
1:52:48 Различных весов немного. Если различных весов $k$, то суммарный вес не меньше $1+2+\dots+k=\frac{k(k+1)}2$; эта величина не больше $W$, поэтому $k\le\sqrt{2W}$ (1:52:48–1:53:40).
1:54:13 Первая мысль: если вес $x$ встречается $k_x$ раз, то в динамике $dp_s$ обновляется через $dp_{s-jx}$ для $j\le k_x$ — это «скользящее окно с шагом $x$». Можно сгруппировать суммы с одинаковым остатком по модулю $x$ и считать максимум в окне длины $k_x+1$ (очередью с максимумом) (1:55:16–1:57:52). Для версии (б) придётся ещё и учитывать число предметов, и группировки неудобны (1:57:52–1:58:24).
1:58:28 Версия (а): склеивание. Для версии (а) сами предметы не важны, можно менять набор, лишь бы множество достижимых сумм не изменилось. Если вес $x$ встречается хотя бы три раза, заменим два предмета веса $x$ одним предметом веса $2x$. Это корректно: при $k$ копиях веса $x$ мы набираем $0,\dots,kx$ кратные $x$ суммы; после замены на $2x$ и $k-2$ копий $x$ можно набрать $0\dots(k-2)x$, затем $(k-1)x$ как $2x$ плюс $k-3$ копий (здесь нужны хотя бы три предмета), и $kx$ как $2x$ плюс все остальные (1:58:35–2:00:27). Повторяем, пока какой-нибудь вес встречается $\ge3$ раз; это удобно делать, обходя веса по возрастанию и держа массив счётчиков (2:00:41–2:01:33).
2:01:35 В конце каждый вес встречается не более двух раз. Если предметов $K$, то их суммарный вес не меньше удвоенной суммы от $1$ до $K/2$, примерно $K^2/8$; значит $K\le2\sqrt{2W}$ — то есть $O(\sqrt W)$ предметов (а не только различных весов) (2:01:45–2:03:05). После этого запускаем обычную динамику рюкзака «по предмету»: $O(\sqrt W)$ предметов, каждый обновляет массив длины $W$ — всего $O(W\sqrt W)$ (2:03:05–2:03:41).
// если вес x встречается ≥ 3 раз, два предмета x заменяем одним 2x
vector<char> reachable_sums(vector<int> w, int W) {
vector<int> cnt(W + 1, 0);
for (int x : w) cnt[x]++;
vector<int> items;
for (int x = 1; x <= W; x++) {
while (cnt[x] >= 3) { cnt[x] -= 2; if (2 * x <= W) cnt[2 * x]++; } // 2x > W недостижим
for (int i = 0; i < cnt[x]; i++) items.push_back(x);
}
vector<char> dp(W + 1, 0); dp[0] = 1;
for (int x : items) for (int s = W; s >= x; s--) if (dp[s - x]) dp[s] = 1;
return dp;
}2:03:41 Версия (б). Для минимального числа предметов склеивание не работает: новый предмет $2x$ на самом деле составлен из двух исходных, и у предметов появляется «стоимость». Если нужно набрать нечётную сумму, мы обязаны взять оставшийся $x$; для чётной — наоборот. Предмет минимальной стоимости оказывается «спрятан» внутри склейки, и динамика ломается (2:03:51–2:07:22).
2:08:18 Другое преобразование: двоичное разбиение. Допустим, у нас только вес $x$, и он встречается $k$ раз. Вместо склеивания превратим их в предметы $x,\,2x,\,4x,\dots,2^Lx$ и остаток (2:08:25–2:09:39). Эти предметы всё ещё позволяют набрать любую сумму, кратную $x$, до $kx$: любой подмножеством первых предметов мы набираем все $0\dots(2^{L+1}-1)x$, а остаток сдвигает диапазон до $kx$ (2:09:47–2:10:35).
2:10:45 Сколько предметов получится. Для каждого различного $x$, встречающегося $k_x$ раз, получаем не больше $\log_2k_x+2$ предметов, то есть всего $\sum_x(\log_2k_x+2)$. Грубая оценка даёт $\sqrt W\log W$ предметов (2:10:41–2:12:06). Но на самом деле лучше: двойки в сумме дают $O(\sqrt W)$ (по одной на каждый различный вес), а $\sum_x\log_2k_x$ перепишем как $\sum_{l\ge1}\#\{x:\ k_x\ge2^l\}$. Различные $x$, встречающиеся хотя бы $2^l$ раз, в сумме $\sum x\cdot2^l\le W$, откуда их не больше $\sqrt{2W/2^l}$. Слагаемые убывают как геометрическая прогрессия со знаменателем $1/\sqrt2$, значит сумма равна $O(\sqrt W)$ (2:12:10–2:17:22). Лектор отмечает: «эта идея работает даже лучше, чем корень на логарифм».
2:17:22 Получилось $O(\sqrt W)$ предметов с различными весами, поэтому динамику можно решить за $O(W\sqrt W)$ (2:17:22–2:17:53).
// минимальное число предметов: k копий веса x дробим на пачки 1,2,4,... и остаток; пачка из c копий стоит c
vector<int> min_items(vector<int> w, int W) {
map<int,int> k; for (int x : w) k[x]++;
vector<pair<int,int>> packs; // (вес, число предметов в пачке)
for (auto [x, c] : k) {
int p = 1;
while (c > 0) { int t = min(p, c); packs.push_back({x * t, t}); c -= t; p *= 2; }
}
const int INF = 1e9;
vector<int> dp(W + 1, INF); dp[0] = 0;
for (auto [pw, pc] : packs) for (int s = W; s >= pw; s--) if (dp[s - pw] < INF) dp[s] = min(dp[s], dp[s - pw] + pc);
return dp;
}2:18:05 Дальше идёт серия задач про массив, где «странные» запросы приходят с разной частотой, и нужно, чтобы редкие операции были долгими, а частые — мгновенными (2:18:05–2:19:19).
2:18:36 (а) Точечное прибавление за $O(1)$, сумма на отрезке за $O(\sqrt n)$. Если бы мы взяли дерево Фенвика, у обеих операций было бы по логарифму. Здесь ценой замедления запросов суммы ускоряем прибавление. Разобьём массив на блоки длины $K$ и в каждом блоке храним сумму. Прибавление в точке меняет сам элемент и сумму его блока ($O(1)$). Запрос суммы — это либо подотрезок одного блока (длина не больше $K$), либо суффикс одного блока, несколько целых блоков и префикс другого — не больше $n/K+2K$ слагаемых (2:19:44–2:22:08). Лектор подчёркивает не забывать второй случай, когда отрезок целиком внутри блока (2:21:42–2:21:48). Оптимально $K=\sqrt n$ (2:22:11).
struct BlockSum {
int n, K; vector<ll> a, bs;
BlockSum(int n, int K) : n(n), K(K), a(n, 0), bs(n / K + 1, 0) {}
void add(int i, ll x) { a[i] += x; bs[i / K] += x; } // O(1)
ll sum(int l, int r) { // [l, r]
ll s = 0;
while (l <= r && l % K) s += a[l++];
while (l + K - 1 <= r) { s += bs[l / K]; l += K; }
while (l <= r) s += a[l++];
return s;
}
};2:22:25 (б) Наоборот: прибавление за $O(\sqrt n)$, сумма за $O(1)$. Для каждого блока храним префиксные суммы внутри блока и префиксные суммы по блокам. Прибавление пересчитывает префиксные суммы внутри блока ($O(K)$) и суммы по блокам ($O(n/K)$). Запрос — разность двух префиксных сумм, что на длинных запросах даёт «сумму сумм в блоках» за $O(1)$ (2:22:34–2:24:33). Снова оптимально $K=\sqrt n$, чтобы обе части работали одинаково (2:24:33).
2:24:47 (в) Арифметическая прогрессия на отрезке за $O(1)$, сумма за $O(\sqrt n)$. Операция: на отрезке $[l,r]$ прибавить прогрессию $b,\ b+c,\ b+2c,\dots$ (2:24:54–2:25:23). Три наблюдения лектора:
left по блокам) и «ко всем элементам внутри блока левее позиции $p$ нужно добавить столько-то» (2:32:50–2:33:20, 2:34:50–2:35:23).2:33:20 Запрос суммы идёт по блокам справа налево и накапливает суммарную добавку от обновлений, лежащих правее; для целого блока его новая сумма определяется за $O(1)$ по накопленным значениям и размеру блока. Для частичных блоков честно проходим по их элементам справа налево, накапливая «левые» добавки внутри блока (2:33:20–2:35:41). Лектор замечает, что именно арифметичность «добавляет олимпиадности» — это не самая интеллектуальная часть, главное — свести к префиксу (2:38:03–2:38:29).
// prefix(p, b, c): ко всем i ≤ p прибавить b + c·i. Отрезок [l, r] = prefix(r) − prefix(l−1).
struct APBlocks {
int n, K, nb; vector<ll> a, bs; // a — исходный массив, bs — его суммы по блокам
vector<ll> lb, lc; // для блока j: прибавить ВСЕМ блокам левее j
vector<ll> ib, ic; // для позиции p: прибавить всем элементам ≤ p в том же блоке
vector<ll> ex; // готовая добавка к сумме блока от prefix-обновлений внутри него
APBlocks(const vector<ll>& init, int K) : n(init.size()), K(K), nb((n + K - 1) / K), a(init), bs(nb, 0), lb(nb, 0), lc(nb, 0), ib(n, 0), ic(n, 0), ex(nb, 0) {
for (int i = 0; i < n; i++) bs[i / K] += a[i];
}
ll idxsum(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }
void prefix(int p, ll b, ll c) {
if (p < 0) return;
int j = p / K, st = j * K;
lb[j] += b; lc[j] += c;
ib[p] += b; ic[p] += c;
ex[j] += b * (p - st + 1) + c * idxsum(st, p);
}
void update(int l, int r, ll b, ll c) { // a[i] += b + c·i на [l, r]
prefix(r, b, c); prefix(l - 1, -b, -c);
}
ll sum(int l, int r) {
ll res = 0, B = 0, C = 0; // накопленные добавки от блоков правее текущего
for (int j = nb - 1; j >= 0; j--) {
int st = j * K, en = min(n, st + K) - 1;
if (st > r) { B += lb[j]; C += lc[j]; continue; }
if (en < l) break; // левее запроса — ничего не нужно
if (l <= st && en <= r) {
ll s = bs[j] + ex[j]; // O(1) на целый блок
s += B * (en - st + 1) + C * idxsum(st, en);
res += s;
} else { // частичный блок: идём справа налево, копим ib/ic внутри блока
ll bb = 0, cc = 0;
for (int i = en; i >= st; i--) {
bb += ib[i]; cc += ic[i];
if (l <= i && i <= r) res += a[i] + bb + cc * i + B + C * i;
}
}
B += lb[j]; C += lc[j];
}
return res;
}
};bs и добавки ex, которую обновление наращивает сразу.2:38:58 Задача. Множество (мультимножество) целых чисел от $0$ до $M$. Операции: вставить, удалить, найти минимум, найти $k$-ю порядковую статистику. Предлагается делать вставку и удаление за $O(1)$, а два запроса — за $O(\sqrt M)$ (2:38:58–2:40:23).
2:40:48 Решение «массив подсчёта»: cnt[x]++ и cnt[x]--, а минимум и $k$-ю статистику ищем проходом слева направо. Чтобы ускорить, храним ещё сумму по блокам. Для $k$-й статистики идём по блокам, пока сумма меньше $k$, затем внутри блока (2:41:18–2:42:44). Минимум — это первая порядковая статистика, поэтому устроен так же (2:42:44–2:43:04). Размер блока снова корень (2:43:04–2:43:11).
struct SqrtSet {
int M, K; vector<int> cnt, bc;
SqrtSet(int M, int K) : M(M), K(K), cnt(M, 0), bc(M / K + 1, 0) {}
void insert(int x) { cnt[x]++; bc[x / K]++; }
void erase(int x) { cnt[x]--; bc[x / K]--; }
int kth(int k) { // k = 1 — минимум
int j = 0;
while (k > bc[j]) { k -= bc[j]; j++; }
for (int x = j * K; ; x++) { if (k <= cnt[x]) return x; k -= cnt[x]; }
}
};2:43:32 Задача. Массив; запросы: прибавить число на отрезке; найти на отрезке количество элементов, не больших $x$ (2:43:50–2:44:57). Сначала лектор предлагает подумать «в оффлайне» и разбить массив на блоки (2:45:27–2:45:57).
2:48:37 Время. Обновление — $O(K+n/K)$. Запрос — $O(K)$ для двух краёв плюс $O\bigl(\tfrac nK\log n\bigr)$ на бинарные поиски. Здесь впервые нужно выбирать нетривиальный параметр: минимизируем $K+\frac nK\log n$, откуда $K=\sqrt{n\log n}$, и время запроса — $O(\sqrt{n\log n})$ (2:48:46–2:49:40).
struct SortedBlocks {
int n, K, nb; vector<ll> a, mod; vector<vector<int>> ord; // ord[j] — индексы блока по возрастанию a
SortedBlocks(const vector<ll>& v, int K) : n(v.size()), K(K), nb((n + K - 1) / K), a(v), mod(nb, 0), ord(nb) { for (int j = 0; j < nb; j++) rebuild(j); }
void rebuild(int j) {
int st = j * K, en = min(n, st + K);
ord[j].resize(en - st); iota(ord[j].begin(), ord[j].end(), st);
sort(ord[j].begin(), ord[j].end(), [&](int x, int y) { return a[x] < a[y]; });
}
void partial(int j, int l, int r, ll x) { // прибавить x к a[l..r] внутри блока j: два отсортированных куска сливаем
vector<int> in, out;
for (int i : ord[j]) (l <= i && i <= r ? in : out).push_back(i);
for (int i = l; i <= r; i++) a[i] += x;
ord[j].clear();
merge(in.begin(), in.end(), out.begin(), out.end(), back_inserter(ord[j]), [&](int p, int q) { return a[p] < a[q]; });
}
void add(int l, int r, ll x) {
int jl = l / K, jr = r / K;
if (jl == jr) { partial(jl, l, r, x); return; }
partial(jl, l, (jl + 1) * K - 1, x);
partial(jr, jr * K, r, x);
for (int j = jl + 1; j < jr; j++) mod[j] += x; // целый блок: порядок не меняется
}
int count_le(int l, int r, ll x) {
int jl = l / K, jr = r / K, res = 0;
auto brute = [&](int a_, int b_) { for (int i = a_; i <= b_; i++) res += a[i] + mod[i / K] <= x; };
if (jl == jr) { brute(l, r); return res; }
brute(l, (jl + 1) * K - 1); brute(jr * K, r);
for (int j = jl + 1; j < jr; j++) { // бинарный поиск по x − modifier
ll t = x - mod[j];
int lo = 0, hi = ord[j].size();
while (lo < hi) { int m = (lo + hi) / 2; if (a[ord[j][m]] <= t) lo = m + 1; else hi = m; }
res += lo;
}
return res;
}
};const int K = 800, а не вычисляют по формуле. Из асимптотики получаем формулу, считаем её явно для максимального теста и записываем число в код (2:50:20–2:51:12). На меньших тестах решение, как ожидается, работает не хуже.2:54:24 Задача. Есть множество (мультимножество) чисел от $0$ до $M$. Запросы: добавить число, удалить число, и для числа $S$ найти число способов представить его в виде суммы двух чисел множества, то есть число пар $(x,y)$ с $x+y=S$ (2:54:24–2:55:41). Через массив подсчёта cnt ответ равен
$$\sum_{x=0}^{S}\mathrm{cnt}[x]\cdot\mathrm{cnt}[S-x]$$
(лектор считает, что учитываются обе упорядоченные пары) (2:55:47–2:56:34).
2:56:34 Статичное множество. Если сначала приходят только добавления, а потом запросы, то эта формула — коэффициент при $y^S$ в квадрате многочлена $\sum_x\mathrm{cnt}[x]\,y^x$, то есть свёртка; она считается быстрым преобразованием Фурье за $O(M\log M)$ сразу для всех $S$ (для $S>2M$ ответ нулевой) (2:57:25–2:59:44).
2:59:51 Но множество меняется. Смотрим, как меняется ответ при добавлении числа $x$: ответ для $S$ увеличивается на число вхождений $S-x$ (3:00:14–3:00:50). Идея — разбить запросы на блоки (3:01:01–3:01:21):
3:03:27 Запрос работает за $O(K)$, перестроение — за $O(M\log M)$ раз в $K$ запросов; значит, общее время на запрос $O(K+\tfrac{M\log M}{K})$ и $K=\sqrt{M\log M}$ (3:03:27–3:05:15). Лектор отмечает, что здесь можно работать даже онлайн: ничего от оффлайна не требуется (3:05:15–3:05:29). Важны не размер множества, а значения чисел — степень многочлена (3:04:12–3:04:31).
// свёртка массива с самим собой (здесь наивная, в решении — БПФ за M log M)
vector<ll> convolve(const vector<ll>& c) { int M = c.size(); vector<ll> r(2 * M, 0); for (int i = 0; i < M; i++) if (c[i]) for (int j = 0; j < M; j++) r[i + j] += c[i] * c[j]; return r; }// «сколько упорядоченных пар (x, y) из мультимножества дают x + y = S»; полная пересборка раз в K изменений
struct TwoSum {
int M; vector<ll> cnt, snapshot, base; vector<pair<int,int>> pend; // pend: (знак, x) изменения после последней сборки
TwoSum(int M) : M(M), cnt(M, 0) { rebuild(); }
void rebuild() { snapshot = cnt; base = convolve(snapshot); pend.clear(); }
void change(int sign, int x) { cnt[x] += sign; pend.push_back({sign, x}); } // вызывающий пересобирает каждые K изменений
ll query(int S) {
ll res = base[S];
for (auto [sg, x] : pend) { // вклад одного изменения: sg · 2 · snapshot[S−x] (+ сама пара x,x)
int y = S - x;
ll other = (y >= 0 && y < M) ? snapshot[y] : 0;
res += (y == x) ? sg * (2 * other + sg) : sg * 2 * other;
snapshot[x] += sg; // следующее изменение видит предыдущие
}
for (int i = (int)pend.size() - 1; i >= 0; i--) snapshot[pend[i].second] -= pend[i].first; // откат
return res;
}
};3:05:44 Задача. Запросы по отрезку $[l,r]$: найти сумму разностей индексов всех пар равных элементов на отрезке: $\sum_{i<j,\ a_i=a_j}(j-i)$ (3:05:44–3:06:57). Делить отрезок на подотрезки здесь невыгодно: разности нужно как-то объединять между подотрезками, так что «никакие деревья, разбивающие массив, нам особо не помогут» (3:09:25–3:09:59). Но за $O(\text{длина отрезка})$ ответ посчитать можно (3:09:59–3:10:12).
3:11:01 Как меняется ответ при сдвиге границы. Если от $[l,r]$ перейти к $[l,r+1]$ и добавить число $a$ на индексе $r+1$, то нужно знать количество вхождений этого числа на отрезке и сумму индексов этих вхождений: добавится $(r+1)\cdot\mathrm{cnt}-\mathrm{sumIdx}$ (3:11:22–3:12:12). Значит, храним два массива: по значению — сколько раз оно встретилось и сумма индексов (3:12:38–3:12:59). Так же пересчитываются добавление слева и удаления.
3:13:06 Алгоритм. Разбиваем массив на блоки длины $K$ и сортируем запросы по блоку левой границы, а внутри блока — по правой границе (3:13:16–3:14:12). Тогда:
3:17:12 Итого $O\!\bigl(\tfrac{n^2}K+qK\bigr)$. Минимум достигается при $K=\tfrac{n}{\sqrt q}$, и время работы — $O(n\sqrt q)$ (3:17:20–3:18:14).
vector<ll> mo_pairs(const vector<int>& a, const vector<array<int,3>>& qs /* l, r, id */) {
int n = a.size(), q = qs.size();
int K = max(1, (int)(n / sqrt((double)max(1, q))));
vector<int> ord(q); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) {
int bx = qs[x][0] / K, by = qs[y][0] / K;
if (bx != by) return bx < by;
return (bx & 1) ? qs[x][1] > qs[y][1] : qs[x][1] < qs[y][1];
});
vector<ll> cnt(n + 1, 0), sidx(n + 1, 0), ans(q);
ll cur = 0; int L = 0, R = -1;
auto addR = [&](int i) { cur += (ll)i * cnt[a[i]] - sidx[a[i]]; cnt[a[i]]++; sidx[a[i]] += i; }; // новые пары: i − j для j в отрезке
auto addL = [&](int i) { cur += sidx[a[i]] - (ll)i * cnt[a[i]]; cnt[a[i]]++; sidx[a[i]] += i; }; // j − i
auto delR = [&](int i) { cnt[a[i]]--; sidx[a[i]] -= i; cur -= (ll)i * cnt[a[i]] - sidx[a[i]]; };
auto delL = [&](int i) { cnt[a[i]]--; sidx[a[i]] -= i; cur -= sidx[a[i]] - (ll)i * cnt[a[i]]; };
for (int id : ord) {
int l = qs[id][0], r = qs[id][1];
while (R < r) addR(++R);
while (L > l) addL(--L);
while (R > r) delR(R--);
while (L < l) delL(L++);
ans[qs[id][2]] = cur;
}
return ans;
}3:20:31 Задача. Дано дерево, на рёбрах записаны неотрицательные целые числа. Запросы по паре вершин $(u,v)$ — найти что-то по числам на пути между ними. Условие в записи звучит невнятно; по тому, какая структура строится в решении (вставка, удаление и поиск первого отсутствующего числа за $O(\sqrt{\ })$), это mex — наименьшее неотрицательное число, которого нет на пути (3:20:31–3:21:42, 3:26:41–3:27:54).
3:21:59 Эйлеров обход. Построим обход в глубину и выпишем в порядок обхода каждое ребро дважды: когда спускаемся по нему и когда поднимаемся (3:22:07–3:22:47). Для вершины $v$ запомним индекс первого ребра, которое «начинается» в $v$ (3:22:47–3:23:08). Утверждается: для вершин $u$ и $v$ на отрезке этого списка между ними рёбра пути встречаются ровно один раз, а все остальные — ноль или два раза (3:23:08–3:24:52).
3:24:52 Поэтому можно применять тот же алгоритм Мо, но поддерживать в структуре только числа, которые встречаются нечётное число раз: если число пришло второй раз, его нужно «выключить» (удалить из структуры) (3:25:04–3:25:51). Структура должна уметь вставлять, удалять и находить mex (3:26:09–3:26:41).
3:26:41 Структура для mex. Корневая: массив подсчёта плюс для каждого блока значений количество присутствующих значений («нулей» нет). Вставка и удаление — $O(1)$; mex ищется пропуском целиком заполненных блоков, а затем проходом по первому неполному блоку — $O(\sqrt{}\,)$ (3:26:51–3:27:54).
3:27:54 Почему не «красивая» структура на логарифм. Запросов mex всего $q$ — по одному на запрос; а вставок и удалений получается столько, сколько сдвигов указателей в Мо (как мы выше подбирали параметры — порядка $n\sqrt q$). С set каждая вставка стоила бы логарифм, умножаясь на более долгую часть; с корневой структурой она стоит $O(1)$, а долгие операции $O(\sqrt{})$ делаются только на ответах (3:27:54–3:29:19).
// mex чисел на пути в дереве: алгоритм Мо по эйлерову обходу с обновлениями
// структура: добавить/убрать значение за O(1), mex за O(sqrt V)
struct SqrtMex {
int V, B; vector<int> cnt, nz; // nz[j] — сколько значений блока j присутствуют
SqrtMex(int V) : V(V), B(max(1, (int)sqrt((double)V))), cnt(V, 0), nz(V / B + 1, 0) {}
void add(int x) { if (cnt[x]++ == 0) nz[x / B]++; }
void del(int x) { if (--cnt[x] == 0) nz[x / B]--; }
int mex() {
int j = 0;
while ((j + 1) * B <= V && nz[j] == B) j++; // полностью заполненные блоки пропускаем
int x = j * B;
while (x < V && cnt[x]) x++;
return x;
}
};3:29:24 Числа в вершинах, а не на рёбрах. Свести к предыдущей задаче можно так: число вершины записать на ребро от неё к родителю. Тогда на пути окажутся числа всех вершин, кроме верхней (3:32:00–3:33:46). Значит, перед ответом на запрос нужно добавить число вершины LCA (а после ответа убрать). На асимптотику это не влияет: одна вставка и одно удаление за $O(1)$; потребуется лишь найти LCA любимым способом (3:34:04–3:34:52).
3:35:01 Обновления: Мо с временем. Теперь добавим запросы изменения чисел. Запрос — это точка в пространстве «левая граница, правая граница, время» $(l,r,t)$, где $t$ — число уже выполненных изменений (3:35:01–3:36:08). Сдвиг по времени на единицу — применить или откатить одно изменение. Сортируем запросы по блоку левой границы, затем по блоку времени, затем по правой границе (3:36:08–3:36:56).
3:38:01 Приравнивая $\tfrac{n^2q}{K^2}$ к $qK$, получаем $K=n^{2/3}$ и время $O(q\,n^{2/3})$; при $n=q$ — $O(n^{5/3})$ сдвигов (3:38:01–3:39:07).
vector<int> path_mex(int n, const vector<vector<int>>& g, vector<int> val,
const vector<array<int,3>>& ops /* {1,u,v} или {2,x,newval} */) {
// эйлеров обход: каждая вершина встречается дважды
vector<int> tin(n), tout(n), ev, par(n, -1), depth(n, 0);
vector<vector<int>> up(18, vector<int>(n, 0));
{ // итеративный обход
vector<pair<int,int>> st = {{0, 0}};
tin[0] = 0; ev.push_back(0);
while (!st.empty()) {
auto& [v, i] = st.back();
if (i < (int)g[v].size()) {
int u = g[v][i++];
if (u == par[v]) continue;
par[u] = v; depth[u] = depth[v] + 1; tin[u] = ev.size(); ev.push_back(u); st.push_back({u, 0});
} else { tout[v] = ev.size(); ev.push_back(v); st.pop_back(); }
}
}
for (int v = 0; v < n; v++) up[0][v] = par[v] < 0 ? v : par[v];
for (int k = 1; k < 18; k++) for (int v = 0; v < n; v++) up[k][v] = up[k - 1][up[k - 1][v]];
auto lca = [&](int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 17; k >= 0; k--) if (depth[a] - (1 << k) >= depth[b]) a = up[k][a];
if (a == b) return a;
for (int k = 17; k >= 0; k--) if (up[k][a] != up[k][b]) { a = up[k][a]; b = up[k][b]; }
return up[0][a];
};
vector<Query> qs; vector<array<int,3>> upd; vector<int> cur = val; // upd: {вершина, старое, новое}
int answers = 0;
for (auto& op : ops) {
if (op[0] == 2) { upd.push_back({op[1], cur[op[1]], op[2]}); cur[op[1]] = op[2]; }
else {
int u = op[1], v = op[2];
if (tin[u] > tin[v]) swap(u, v);
int l = lca(u, v);
if (l == u) qs.push_back({tin[u], tin[v], (int)upd.size(), -1, answers++});
else qs.push_back({tout[u], tin[v], (int)upd.size(), l, answers++});
}
}
int N = ev.size(), K = max(1, (int)cbrt((double)N * N));
sort(qs.begin(), qs.end(), [&](const Query& a, const Query& b) {
if (a.l / K != b.l / K) return a.l / K < b.l / K;
if (a.r / K != b.r / K) return a.r / K < b.r / K;
return a.t < b.t;
});
SqrtMex M(n + 1); vector<char> used(n, 0); vector<int> res(answers);
auto toggle = [&](int v) { if (used[v]) { M.del(val[v]); used[v] = 0; } else { M.add(val[v]); used[v] = 1; } };
auto apply = [&](int i, bool forward) {
int x = upd[i][0], to = forward ? upd[i][2] : upd[i][1];
if (used[x]) { M.del(val[x]); M.add(to); }
val[x] = to;
};
int L = 0, R = -1, T = 0;
for (auto& q : qs) {
while (T < q.t) apply(T++, true);
while (T > q.t) apply(--T, false);
while (L > q.l) toggle(ev[--L]);
while (R < q.r) toggle(ev[++R]);
while (L < q.l) toggle(ev[L++]);
while (R > q.r) toggle(ev[R--]);
if (q.extra >= 0) toggle(q.extra); // вершина LCA не лежит в отрезке: добавляем её на время ответа
res[q.id] = M.mex();
if (q.extra >= 0) toggle(q.extra);
}
return res;
}SqrtMex.3:39:22 Задача. Массив; запросы $[l,r]$ — найти максимальный подотрезок с нулевой суммой (длину), время такое же, как в Мо (3:39:22–3:40:25). Считаем префиксные суммы $p$: сумма на отрезке нулевая, если $p_y=p_x$; нужна максимальная разность $y-x$ среди равных значений на отрезке префиксов $[l,r+1]$ (3:42:44–3:44:59).
3:45:57 Индексы добавляются и удаляются только с краёв (Мо), поэтому для каждого значения префикса можно хранить дек индексов (в отсортированном порядке): первое и последнее вхождения — это пара, дающая максимальную разность (3:46:09–3:47:21). При удалении же нужно поддерживать максимум всех этих разностей — например, множеством, а это логарифм (3:47:45–3:49:16).
3:49:23 Если элементы только добавляются, всё проще: ответ только растёт, поэтому достаточно хранить одну переменную ответа и при каждом добавлении индекса $R$ делать ans = max(ans, R - первое вхождение такого же префикса); так же при добавлении слева (3:49:29–3:51:11). Отсюда Мо без удалений (3:51:21):
3:53:41 Если структура умеет добавлять за $O(1)$, то откат тоже $O(1)$ на элемент (удалять можно только последний добавленный), и общее время остаётся прежним: $O(n\sqrt q)$ (3:53:41–3:55:27). Запросы, целиком лежащие в одном блоке, — отдельный случай: если вставка за $O(1)$, то на такой запрос хватает $O(K)$ (3:55:37–3:56:33).
vector<int> mo_rollback_zero(const vector<ll>& a, const vector<array<int,2>>& qs) {
int n = a.size(), q = qs.size();
vector<ll> p(n + 1, 0); for (int i = 0; i < n; i++) p[i + 1] = p[i] + a[i]; // нужна пара x<y из [l, r+1] с p[x]=p[y]
vector<ll> vals(p.begin(), p.end()); sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end());
vector<int> id(n + 1); for (int i = 0; i <= n; i++) id[i] = lower_bound(vals.begin(), vals.end(), p[i]) - vals.begin();
int K = max(1, (int)(n / sqrt((double)max(1, q))));
vector<int> ord(q); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) { int bx = qs[x][0] / K, by = qs[y][0] / K; return bx != by ? bx < by : qs[x][1] < qs[y][1]; });
vector<int> ans(q, 0), first(vals.size(), -1), last(vals.size(), -1);
vector<int> first2(vals.size(), -1);
auto inblock = [&](int l, int r) { // запрос целиком в одном блоке: добавляем префиксы l..r+1 слева направо, за O(K)
int best = 0;
for (int x = l; x <= r + 1; x++) { int v = id[x]; if (first2[v] < 0) first2[v] = x; best = max(best, x - first2[v]); }
for (int x = l; x <= r + 1; x++) first2[id[x]] = -1;
return best;
};
int curBlock = -1, R = 0, ans0 = 0; // в структуре лежат индексы префиксов (blockEnd .. R]
for (int qi : ord) {
int l = qs[qi][0], r = qs[qi][1], b = l / K;
if (r / K == b) { ans[qi] = inblock(l, r); continue; } // запрос внутри одного блока
if (b != curBlock) { // новый блок: чистим структуру
fill(first.begin(), first.end(), -1); fill(last.begin(), last.end(), -1);
curBlock = b; R = (b + 1) * K - 1; ans0 = 0; // граница блока: индексы префиксов > R пока не добавлены
// структура пуста; R+1 — первый добавляемый индекс префикса
}
while (R + 1 <= r + 1) { // добавляем справа: индекс префикса R+1
++R; int v = id[R];
if (first[v] < 0) first[v] = R;
last[v] = R; ans0 = max(ans0, last[v] - first[v]);
}
// временно добавляем слева индексы префиксов l .. (b+1)K − 1 (в обратном порядке), потом откатываем
vector<array<int,3>> undo; int ansTmp = ans0;
for (int x = (b + 1) * K - 1; x >= l; x--) {
int v = id[x];
undo.push_back({v, first[v], last[v]});
if (last[v] < 0) last[v] = x;
first[v] = x; ansTmp = max(ansTmp, last[v] - first[v]);
}
ans[qi] = ansTmp;
for (int i = (int)undo.size() - 1; i >= 0; i--) { first[undo[i][0]] = undo[i][1]; last[undo[i][0]] = undo[i][2]; }
}
return ans;
}3:57:44 Задача 12. Дана таблица чисел с шахматной раскраской. Нужно найти максимальную по площади прямоугольную подтаблицу, в которой сумма чисел белых клеток равна сумме чисел чёрных (3:57:44–3:58:38). Время нужно $O(\ (nm)^{3/2}\ )$ — «корневое» (3:59:00–3:59:19).
3:59:19 Упрощение. Умножим числа чёрных клеток на $-1$: задача превращается в поиск максимального прямоугольника с нулевой суммой (3:59:19–4:00:07). Для одной строки (полоски) это ровно предыдущая задача: считаем префиксные суммы, идём слева направо и храним для каждого значения префикса его первое вхождение в хеш-таблице; ответ — максимум разности индексов (4:01:52–4:02:41).
4:04:12 От прямоугольника к полоске. Прямоугольник — отрезок по одной координате и отрезок по другой. Переберём отрезок строк, сложим выбранные строки в одну полоску и решим задачу для неё. Получается $O(n^2m)$ (4:04:47–4:06:16). Но таблицу можно перевернуть и перебирать отрезки столбцов — $O(nm^2)$; берём лучший вариант: время $O\bigl(nm\cdot\min(n,m)\bigr)$, а так как $\min(n,m)\le\sqrt{nm}$, это $O\bigl((nm)^{3/2}\bigr)$ (4:06:18–4:07:18).
int max_zero_rect(vector<vector<ll>> g) {
int n = g.size(), m = g[0].size();
if (n > m) { // транспонируем: перебираем пары строк у короткой стороны
vector<vector<ll>> t(m, vector<ll>(n));
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) t[j][i] = g[i][j];
g = t; swap(n, m);
}
int best = 0;
for (int top = 0; top < n; top++) {
vector<ll> col(m, 0);
for (int bot = top; bot < n; bot++) {
for (int j = 0; j < m; j++) col[j] += g[bot][j];
unordered_map<ll,int> firstPos; firstPos[0] = 0; ll s = 0;
for (int j = 0; j < m; j++) {
s += col[j];
auto it = firstPos.find(s);
if (it == firstPos.end()) firstPos[s] = j + 1;
else best = max(best, (bot - top + 1) * (j + 1 - it->second));
}
}
}
return best;
}4:08:40 Некоторые задачи с листочков остались неразобранными; их разберут позже. Контест уже доступен, и онлайн-вопросов нет (4:08:40–4:09:17).