3:09 Запись начинается с проверки звука и разговора о контесте (3:09–6:41); содержательный разбор — с 6:41. Ведущий разбирает листочек подряд: первые четыре задачи — это материал лекций по деревьям, поэтому им уделено мало времени. Затем начинается корневая декомпозиция (1:03:37), а во второй половине занятия — «корневая оптимизация» и корневая по запросам.
8:27 Дерево, запросы «присвоить число вершине» и «сумма на пути $v$–$u$». Строим эйлеров обход; присвоение превращаем в «$+=$ в точке» (старое значение запоминаем). Сумма на пути разбивается на три вертикальных пути: $v\to$ корень, $u\to$ корень, $\mathrm{lca}\to$ корень (9:08–9:36).
9:36 Вершина со значением $w$ вносит вклад в сумму до корня у всех вершин своего поддерева. Поэтому в Фенвике на позицию входа вершины добавляем $+w$, а на позицию выхода — $-w$; сумма на вертикальном пути — это префиксная сумма до позиции $v$ включительно (9:36–10:16).
10:31 Сортируем запросы и рёбра по весу (события «ребро» и «запрос $x$»; при равенстве сначала рёбра, ведь знак нестрогий, 11:06–11:21). Ребро, которое «включается», прибавляет $1$ ко всем вертикальным путям, проходящим через него: то есть $+1$ в точке входа нижнего конца и $-1$ в точке выхода, а путь $v$–$u$ снова разбивается на три вертикальных (11:21–12:25). Всего $O((n+q)\log n)$ с Фенвиком.
13:35 Корневое дерево, два запроса: перекрасить всё поддерево $v$ в цвет $c$ (цветов не больше $60$) и найти число различных цветов в поддереве. Эйлеров обход «сводит задачу на дереве к задаче на массиве с отрезками» (13:50–14:17): поддерево — отрезок $[tin_v,\ tout_v)$.
14:54 Дерево отрезков с присвоением на отрезке (массовая операция «присвоить $c$», в детях старые пометки перезатираются) и в каждой вершине — маска присутствующих цветов в одном 64-битном числе. Объединение — побитовое OR; ответ на запрос — OR масок $O(\log n)$ вершин и popcount (15:03–16:42). Цветов мало, поэтому «не нужно умножать на 60»: множество цветов помещается в одно слово (13:05–13:27).
struct ColorTree {
int n; vector<ll> mask; vector<int> lz;
ColorTree(const vector<int>& c) : n(c.size()), mask(4 * c.size(), 0), lz(4 * c.size(), -1) { build(1, 0, n, c); }
void build(int v, int l, int r, const vector<int>& c) {
if (r - l == 1) { mask[v] = 1LL << c[l]; return; }
int m = (l + r) / 2; build(2 * v, l, m, c); build(2 * v + 1, m, r, c); mask[v] = mask[2 * v] | mask[2 * v + 1];
}
void apply(int v, int col) { mask[v] = 1LL << col; lz[v] = col; }
void push(int v) { if (lz[v] >= 0) { apply(2 * v, lz[v]); apply(2 * v + 1, lz[v]); lz[v] = -1; } }
void assign(int v, int l, int r, int ql, int qr, int col) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { apply(v, col); return; }
push(v); int m = (l + r) / 2;
assign(2 * v, l, m, ql, qr, col); assign(2 * v + 1, m, r, ql, qr, col);
mask[v] = mask[2 * v] | mask[2 * v + 1];
}
ll get(int v, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return mask[v];
push(v); int m = (l + r) / 2;
return get(2 * v, l, m, ql, qr) | get(2 * v + 1, m, r, ql, qr);
}
void recolor(int l, int r, int col) { assign(1, 0, n, l, r, col); }
int distinct(int l, int r) { return __builtin_popcountll(get(1, 0, n, l, r)); }
};17:07 Даны два дерева на одних и тех же вершинах. Нужно сосчитать пары $(v,u)$, где $v$ — предок $u$ и в первом, и во втором дереве (17:07–17:42).
19:49 Обходим второе дерево в глубину, а первое пронумеровываем эйлеровым обходом, так что поддерево $v$ в первом дереве — отрезок. В Фенвике по первому дереву храним «вершины, второй раз уже полностью обработанные». Когда заходим в $v$, запоминаем «красное» — сумму на отрезке поддерева $v$ первого дерева (в ней лишнее, пришедшее из прошлых ветвей). Когда выходим из $v$, берём ту же сумму и вычитаем красное: разность — это ровно вершины, добавленные, пока мы были внутри $v$, то есть потомки $v$ во втором дереве, лежащие в поддереве $v$ первого. После этого добавляем $+1$ в позицию самой $v$ (21:09–23:41). Итого $O(n\log n)$.
ll common_ancestor_pairs(const Tree& A, const Tree& Bt) {
int n = A.n; Fen f(n); ll ans = 0;
vector<int> before(n);
vector<pair<int, int>> st{{0, 0}};
before[0] = f.sum(A.tin[0], A.out[0]);
while (!st.empty()) {
int v = st.back().first, i = st.back().second;
if (i < (int)Bt.adj[v].size()) {
st.back().second++;
int u = Bt.adj[v][i];
if (u == Bt.par[v] && v != 0) continue;
before[u] = f.sum(A.tin[u], A.out[u]); // «красное»: что уже было в поддереве u первого дерева
st.push_back({u, 0});
} else {
ans += f.sum(A.tin[v], A.out[v]) - before[v]; // «зелёное»: добавилось, пока мы были внутри v
f.add(A.tin[v], 1);
st.pop_back();
}
}
return ans;
}24:07 Ведущий замечает, что задачу (с Всероса 2016–2017) участники сдавали разреженной таблицей, и обещает рассказать решение без неё (24:07–24:31). Условие в записи пересказано неполно: есть $N$ экспериментов; $i$-й стоит $c_i$ и даёт случайное количество вещества из $[l_i,r_i]$; в любой момент вещества не больше $A$; в конце получаем $x\cdot 10^9-(\text{затраты})$, и нужно максимизировать гарантированную прибыль (24:31–26:22). Стратегия адаптивна: решение зависит от текущего количества вещества (26:55–27:35), поэтому состояние — только количество $x$.
29:41 Пусть $dp_x$ — минимальные гарантированные затраты, чтобы оказаться с $x$ веществом. Перебираем последний эксперимент $i$: до него было $y\in[x-r_i,\ x-l_i]$, худший случай — максимум затрат на этом отрезке: $$dp_x=\min_i\Bigl(c_i+\max_{y\in[x-r_i,\,x-l_i]} dp_y\Bigr),\qquad x-r_i\ge 0,\ x\le A,\quad dp_0=0$$ (34:11–36:01, 42:14–44:05). Ответ — $\max_x\,(x\cdot 10^9-dp_x)$ (44:05–44:34). Левая часть окна неотрицательна, потому что $l_i>0$ и мы строго идём вправо: циклических зависимостей нет (32:40–32:56).
36:44 Остаётся быстро брать максимум на известных отрезках. Берётся «тот самый алгоритм», о котором ведущий рассказывал раньше: стек максимумов + СНМ, когда запросы заранее сгруппированы по правой границе (36:53–38:12). Идём слева направо; элемент, вытесненный из стека более крупным, «приклеивается» к вытеснившему в СНМ, а ответ на $[l,r]$ при правом конце $r$ — значение в корне $l$. Хранить сами запросы явно нельзя (их $N\cdot A$, «по памяти сдохнете»), поэтому их приходится порождать на лету (39:55–40:30); именно эта часть в записи объяснена сжато, и ведущий сам предлагает переспросить, если непонятно (44:34–44:52).
vector<ll> offline_range_max(const vector<ll>& a, const vector<pair<int, int>>& qs) { // отрезки [l, r] включительно
int n = a.size(); vector<vector<pair<int, int>>> byR(n);
for (int i = 0; i < (int)qs.size(); i++) byR[qs[i].second].push_back({qs[i].first, i});
vector<int> par(n), st; iota(par.begin(), par.end(), 0);
function<int(int)> find = [&](int x) { while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; } return x; };
vector<ll> ans(qs.size());
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.back()] <= a[i]) { par[st.back()] = i; st.pop_back(); } // вытесненный элемент «приклеивается» к вытеснившему
st.push_back(i);
for (auto [l, id] : byR[i]) ans[id] = a[find(l)]; // корень l — позиция максимума на [l, i]
}
return ans;
}45:00 Учебная задача на двумерную разреженную таблицу. Пересечение прямоугольников — снова прямоугольник (возможно, пустой): берём максимум левых границ и минимум правых по каждой оси; если левая не меньше правой, пересечение пусто (45:22–46:14). Максимумы и минимумы по подпрямоугольнику таблицы отвечает двумерная разреженная таблица (46:14–46:31).
46:52 В вершинах дерева записаны числа $a_i$; нужно найти $\sum_{i<j,\ a_i=a_j}\mathrm{dist}(i,j)$ (46:52–47:57). Равенство $a_i=a_j$ задаёт классы эквивалентности, поэтому перебирать пары не нужно: фиксируем значение $c$ и берём все вершины $v_1,\dots,v_{k_c}$ с этим значением (48:05–49:47).
50:24 На этих вершинах строим сжатое (виртуальное) дерево — оно содержит не более $2k_c$ вершин. Сумма попарных расстояний в дереве равна $\sum_{e} w_e\cdot s_e\,(k_c-s_e)$, где $s_e$ — число «наших» вершин под ребром $e$ (50:59–52:26). Построение — $O(k_c\log k_c)$, обход — $O(k_c)$; суммируя по значениям, получаем $O(n\log n)$ (52:26–53:15).
ll sum_pair_dist(const Tree& T, vector<int> v) { // сумма расстояний по всем парам различных вершин
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
int k = v.size(); vector<int> nodes, pidx; build_virtual(T, v, nodes, pidx);
vector<ll> cnt(nodes.size(), 0);
for (int x : v) cnt[lower_bound(nodes.begin(), nodes.end(), x, [&](int a, int b) { return T.tin[a] < T.tin[b]; }) - nodes.begin()] = 1;
ll ans = 0;
for (int i = nodes.size() - 1; i >= 1; i--) { // дети всегда имеют больший tin, чем родитель
ans += (ll)(T.dep[nodes[i]] - T.dep[nodes[pidx[i]]]) * cnt[i] * (k - cnt[i]);
cnt[pidx[i]] += cnt[i];
}
return ans;
}53:38 Есть дерево с достопримечательностями в вершинах; путешественники разбивают их на отрезки подряд идущих. Для путешественника с отрезком $[L,R]$ нужно найти, сколько различных вершин он обязан посетить (путь начинается и кончается где угодно) (54:23–55:12).
55:25 Берём вершины, соответствующие достопримечательностям из $[L,R]$ (их не больше $R-L+1$, повторы не мешают), строим на них сжатое дерево. Стартовать нужно с какой-то вершины сжатого дерева (иначе лишний хвост выкинем), и мы обязаны побывать во всех его вершинах. Число вершин — сумма длин (в исходных рёбрах) всех сжатых рёбер плюс один (56:20–58:24). Отрезки не пересекаются, поэтому всё вместе работает за $O(n\log n)$.
int steiner_size(const Tree& T, const vector<int>& v) { // сколько вершин в наименьшем поддереве, содержащем все v
vector<int> nodes, pidx; build_virtual(T, v, nodes, pidx);
int r = 1;
for (size_t i = 1; i < nodes.size(); i++) r += T.dep[nodes[i]] - T.dep[nodes[pidx[i]]];
return r;
}58:49 Вариант про рёбра. Если считать число пройденных рёбер и не обязательно возвращаться, то обход сжатого дерева из корня стоит $2\cdot(\text{число рёбер})$ минус длина пути от старта до конечной вершины; последняя не больше диаметра, поэтому ответ — $2E-\mathrm{diam}$, а диаметр ищется двумя обходами (59:21–1:00:52).
1:01:19 «Число различных цветов в поддереве» для всех вершин сразу: делаем эйлеров обход в прямом порядке, поддерево — отрезок массива, дальше стандартное оффлайн-решение «число различных на отрезках» заметающей прямой и Фенвиком (1:01:19–1:02:17).
1:02:21 Последняя задача — тот же трюк, что в задаче E: запросы «$+=$ в поддереве» и «сумма на пути»; для решения нужны два разных обхода (прямой и обратный) и немного аккуратности. Если решение не придумывается — подойдёт корневая декомпозиция (1:02:30–1:02:55). На этом разбор закончен (1:03:32).
1:04:23 Лектор отмечает, что листочек может показаться простым, но в нём есть интересные задачи (седьмая, десятая–пятнадцатая) и такие полезные вещи, как трёхмерный Мо и Мо на дереве (1:04:34–1:05:30). Идём по листочку сверху вниз.
1:06:04 Массив из $n$ чисел, запросы: присвоить $a_i=x$ и найти сумму на отрезке. Дерево отрезков делает и то и другое за $O(\log n)$, но можно сделать присвоение за $O(1)$, а сумму — за $O(\sqrt n)$ (1:07:21–1:07:45). Лектор рассказывает, что идею «корнячки» можно придумать самому и что Денис Павлович Кириенко придумал её сам на олимпиаде 90-х (1:07:45–1:07:55).
1:08:09 Идея. Разбиваем массив на блоки по $B$ элементов и для каждого блока храним сумму. Изменение элемента: поправить $a_i$ и сумму блока $\lfloor i/B\rfloor$ — $O(1)$ (1:08:09–1:09:10). Запрос $[l,r)$: часть блоков лежит целиком — их суммы добавляем сразу; не более двух блоков задеты частично — у одного суффикс запроса, у другого префикс; их проходим по одному элементу (1:09:15–1:09:57).
1:10:06 Выбор $B$. Запрос стоит $O(B)$ (края) плюс $O(n/B)$ (число блоков). Сумма $B+n/B$ минимальна, когда слагаемые равны: $B=n/B$, то есть $B=\sqrt n$ (1:10:21–1:12:20). Для ноль-индексации номер блока элемента $i$ — это $\lfloor i/B\rfloor$ (1:13:28–1:13:45).
1:13:56 Лаконичная реализация. Идём по $i$ от $l$ до $r$: если $i$ — начало блока и блок целиком помещается ($i+B\le r$), добавляем сумму блока и делаем $i\mathrel{+}=B$; иначе добавляем $a_i$ и делаем $i\mathrel{+}=1$ (1:14:01–1:15:30). Операция взятия остатка там много раз, но почти всегда это приемлемо (1:15:55–1:16:44).
struct BlockSum {
int n, B; vector<ll> a, blk;
BlockSum(const vector<ll>& v) : n(v.size()), B(isqrt_ceil(v.size())), a(v), blk((v.size() + B - 1) / B + 1, 0) {
for (int i = 0; i < n; i++) blk[i / B] += a[i];
}
void assign(int i, ll x) { blk[i / B] += x - a[i]; a[i] = x; } // O(1)
ll sum(int l, int r) { // O(sqrt n)
ll s = 0;
for (int i = l; i < r;) {
if (i % B == 0 && i + B <= r) { s += blk[i / B]; i += B; } // перепрыгнули через целый блок
else { s += a[i]; i++; } // идём по префиксу/суффиксу по одному
}
return s;
}
};1:16:59 Теперь наоборот: запросов суммы много, изменений мало. Нужно хранить префиксные суммы и научиться чинить их за $O(\sqrt n)$ (1:16:59–1:17:31). Изменение $a_i$ меняет все префиксы справа от $i$ на одну и ту же разность. Поэтому делим префиксы на два слоя: в блоке $i$ перестраиваем префиксы внутри блока честно ($\le B$ операций); всем блокам правее заводим «отложенную» добавку к сумме всех предыдущих блоков ($\le n/B$ операций) (1:17:31–1:19:23). Префикс до $i$ — это префикс внутри блока плюс сумма блоков до него, поэтому запрос — $O(1)$.
struct PrefixBlocks {
int n, B; vector<ll> a, in, before; // in[i] — сумма a от начала блока до i включительно; before[b] — сумма всех блоков до b
PrefixBlocks(const vector<ll>& v) : n(v.size()), B(isqrt_ceil(v.size())), a(v), in(v.size()), before((v.size() + B - 1) / B + 1, 0) {
int nb = (n + B - 1) / B;
for (int b = 0; b < nb; b++) {
ll run = 0;
for (int i = b * B; i < min(n, (b + 1) * B); i++) { run += a[i]; in[i] = run; }
before[b + 1] = before[b] + run;
}
}
void add(int i, ll d) {
a[i] += d;
for (int j = i; j < min(n, (i / B + 1) * B); j++) in[j] += d; // свой блок пересчитываем честно
for (int b = i / B + 1; b < (int)before.size(); b++) before[b] += d; // остальным блокам — «отложенная» добавка
}
ll pref(int i) { return i == 0 ? 0 : in[i - 1] + before[(i - 1) / B]; } // сумма a[0..i)
ll sum(int l, int r) { return pref(r) - pref(l); }
};1:19:29 Операции: $+x$ на отрезке и «сколько $a_i\le x$ на отрезке»; желаемая оценка — $O(n+q\sqrt n\ \cdot\text{что-то малое})$ вместо $O(n\log n)$ (1:19:29–1:19:43).
1:19:53 Сначала решаем задачу без прибавления. Блоки храним отсортированными (рядом лежит и исходный массив). Запрос: в целых блоках делаем бинарный поиск, в краях просматриваем элементы по одному. Время запроса $O(B+\frac nB\log B)$ (1:20:05–1:21:49).
1:22:08 Прибавление. Для целиковых блоков прибавляем к метке блока «ко всем элементам блока нужно добавить $x$»; в неполных (их не более двух) изменяем элементы и перестраиваем сортировку блока ($B\log B$). Тогда истинное значение — $a_i+\mathrm{lazy}_{\text{блока}}$, а бинарный поиск ведём по $x-\mathrm{lazy}$ (1:22:16–1:23:20).
struct SortedBlocks {
int n, B; vector<ll> a, lazy; vector<vector<ll>> s; // истинное значение = a[i] + lazy[блок]
SortedBlocks(const vector<ll>& v, int B) : n(v.size()), B(B), a(v), lazy((v.size() + B - 1) / B, 0), s(lazy.size()) {
for (int b = 0; b < (int)s.size(); b++) rebuild(b);
}
void rebuild(int b) { s[b].assign(a.begin() + b * B, a.begin() + min(n, (b + 1) * B)); sort(s[b].begin(), s[b].end()); }
void part(int b, int l, int r, ll x) { for (int i = l; i < r; i++) a[i] += x; rebuild(b); }
void add(int l, int r, ll x) { // [l, r)
if (l >= r) return;
int bl = l / B, br = (r - 1) / B;
if (bl == br) { part(bl, l, r, x); return; }
part(bl, l, (bl + 1) * B, x); part(br, br * B, r, x);
for (int b = bl + 1; b < br; b++) lazy[b] += x;
}
int count_le(int l, int r, ll x) { // сколько a[i] <= x на [l, r)
if (l >= r) return 0;
int bl = l / B, br = (r - 1) / B, res = 0;
auto scan = [&](int lo, int hi) { for (int i = lo; i < hi; i++) res += a[i] + lazy[i / B] <= x; };
if (bl == br) { scan(l, r); return res; }
scan(l, (bl + 1) * B); scan(br * B, r);
for (int b = bl + 1; b < br; b++) res += upper_bound(s[b].begin(), s[b].end(), x - lazy[b]) - s[b].begin();
return res;
}
};1:23:20 Какой $B$ лучше? Если взять $B=\sqrt n$, получим $O(n\sqrt n\log)$. Но запрос — $B+\frac nB\log B$, и слагаемые равны при $B^2=n\log n$ (используется $\log B\approx\log n$). Тогда $B=\sqrt{n\log n}$ и запрос работает за $O(\sqrt{n\log n})$, т.е. логарифм «уехал под корень» (1:24:21–1:26:29). Общий вывод: если работа на целый блок нетривиальна (бинарный поиск и т.п.), блок стоит брать больше $\sqrt n$ (1:26:29–1:26:58).
1:27:03 Эту задачу до корневой не умели решать никак: «$+=$ на отрезке» ломает деревья сортировок (1:27:03–1:27:44).
1:28:52 Отход от корнячки к конструктиву: на плоскости $n$ точек с координатами до $n$; стоим в $(0,0)$, за шаг двигаемся на $1$ вверх/вниз/влево/вправо. Нужно обойти все точки асимптотически быстрее $n^2$ (1:29:00–1:30:51). Подход «граф и кратчайший цикл» не нужен — минимум не требуется, нужен лишь путь, короче квадрата (1:30:35–1:31:01). Обход всей сетки даёт $n^2$ (1:31:07–1:31:20), пропуск пустых столбцов ломается на контрпримере (1:31:42–1:32:30).
1:34:48 Хорошая идея из зала — разбить плоскость на квадраты и обойти их; но в квадрате остаётся та же задача. Лектор разбирает: квадраты со стороной $\sqrt n$ можно пройти змейкой за $O(n)$ шагов между квадратами, а вот что делать внутри — неясно (1:35:08–1:37:04). Идею «тяжёлые/лёгкие квадраты» и «сортировать внутри» лектор доводит до решения, меняя только форму кусков:
1:38:56 Делим плоскость на полосы шириной $B$ (вторая сторона — $n$). Точки сортируем по возрастанию $y$ и обходим по полосам. Время складывается из двух частей: движение по $y$ — не более $n$ на полосу, то есть $\frac nB\cdot n$; движение по $x$ — когда переходим от прошлой точки в той же полосе, сдвиг не более $B$, то есть $n\cdot B$ в сумме (первые точки полос дают ещё $\frac nB\cdot n$) (1:39:18–1:43:46). Итого $O\!\left(\frac{n^2}{B}+nB\right)$, при $B=\sqrt n$ получается $O(n\sqrt n)$ (1:43:46–1:44:04).
vector<int> strip_order(const vector<pair<int, int>>& p, int B, bool snake) {
vector<int> id(p.size()); iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
int bi = p[i].first / B, bj = p[j].first / B;
if (bi != bj) return bi < bj;
if (snake && bi % 2) return p[i].second > p[j].second; // на нечётных полосах идём вниз
return p[i].second < p[j].second;
});
return id;
}1:44:29 Теперь задача: массив неотрицательных чисел, запросы $[l,r]$ — найти $\operatorname{mex}$ значений на отрезке. Дереву отрезков непонятно, что хранить в вершине; в зале предлагают оффлайн, персистентность и последнюю позицию значения — всё это работает на массиве, но потом понадобятся модификации (мекс на пути, изменения), с которыми так не получится (1:44:46–1:45:55).
1:46:05 Решаем вспомогательную задачу: множество с операциями «добавить», «удалить», «найти mex» — для него хватает set недостающих значений и счётчика вхождений, всё за $O(\log n)$ (1:46:05–1:47:16). Ключевое наблюдение: если известен ответ для отрезка, то для соседнего его можно получить, удалив и добавив несколько элементов (1:47:34–1:48:25). Остаётся найти порядок запросов, при котором таких удалений и добавлений мало (1:48:25–1:48:31).
1:48:31 Каждый запрос $[l,r]$ — точка плоскости с координатами $(l,r)$; «сдвинуть границу на единицу» — шаг по плоскости. Мы свели задачу к обходу точек на плоскости предыдущим приёмом (1:48:40–1:49:15). Это и есть алгоритм Мо.
1:49:27 Реализация. Сортируем запросы компаратором: если $l/B$ равны, то по $r$; иначе по $l$ (1:50:14–1:52:24). Текущий отрезок $[L,R)$ изначально пуст (1:54:02–1:54:10). Чтобы не удалять несуществующие элементы, сначала расширяем границы, потом сужаем: четыре цикла (1:53:34–1:54:46).
1:55:00 Змейка. Оптимизация: после первого блока не возвращаться в начало, а на нечётных блоках идти по $r$ в обратную сторону. Достаточно в компараторе для нечётного блока $l/B$ поменять знак сравнения (1:55:23–1:56:22).
vector<int> mo_order(const vector<int>& L, const vector<int>& R, int B, bool snake = true) {
vector<int> id(L.size()); iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
int bi = L[i] / B, bj = L[j] / B;
if (bi != bj) return bi < bj;
return (snake && bi % 2) ? R[i] > R[j] : R[i] < R[j];
});
return id;
}1:56:51 Асимптотика. Двигаем границы $O(n\sqrt q)$ раз (при хорошем $B$), и каждое движение стоит $O(\log n)$ с set. Но запросов самого mex всего $q$, а сдвигов $n\sqrt n$, т.е. нужно научиться делать добавление и удаление за $O(1)$ ценой запроса $O(\sqrt n)$ (1:56:59–1:58:19).
1:58:40 Элементы больше $n$ можно сразу игнорировать: среди $n$ значений mex не превосходит $n$ (1:58:40–1:58:55). Храним массив cnt[v] — сколько раз значение встречается — и делим его на блоки; в каждом блоке храним число нулей (2:00:31–2:01:31). Изменение: при $+1$, если было $0$, уменьшаем счётчик нулей блока; при $-1$, если стало $0$, увеличиваем (2:01:31–2:01:51). Запрос: идём по блокам, пропуская те, где нулей нет, и в первом подходящем блоке ищем ноль честно (2:01:51–2:02:36). Итого $O(\sqrt n)$ на запрос и $O(1)$ на изменение.
struct MexSet {
int V, B; vector<int> cnt, zeros; // zeros[b] — сколько значений в блоке b отсутствуют
MexSet(int V) : V(V), B(isqrt_ceil(V)), cnt(V, 0), zeros((V + B - 1) / B, 0) { for (int v = 0; v < V; v++) zeros[v / B]++; }
void add(int x) { if (x < V && cnt[x]++ == 0) zeros[x / B]--; }
void rem(int x) { if (x < V && --cnt[x] == 0) zeros[x / B]++; }
int mex() const {
int b = 0;
while (b < (int)zeros.size() && zeros[b] == 0) b++; // первый блок, где есть «дырка»
if (b == (int)zeros.size()) return V;
int v = b * B; while (cnt[v]) v++; // внутри блока ищем честно
return v;
}
};// mex на отрезках [l, r] (включительно) алгоритмом Мо
vector<int> mo_mex(const vector<int>& a, const vector<pair<int, int>>& qs) {
int n = a.size(), q = qs.size();
vector<int> L(q), R(q);
for (int i = 0; i < q; i++) { L[i] = qs[i].first; R[i] = qs[i].second; }
MexSet ms(n + 1);
vector<int> ans(q), ord = mo_order(L, R, isqrt_ceil(n));
int l = 0, r = -1; // текущий отрезок [l, r], пока пустой
for (int i : ord) {
while (l > L[i]) ms.add(a[--l]); // сначала расширяем...
while (r < R[i]) ms.add(a[++r]);
while (l < L[i]) ms.rem(a[l++]); // ...потом сужаем
while (r > R[i]) ms.rem(a[r--]);
ans[i] = ms.mex();
}
return ans;
}2:41:59 Так mex на отрезке решается за $O(n\sqrt q+q\sqrt n)$ — «благодаря тому, что внутри Мо применили корнячку» (2:41:59–2:42:26). Перед этим ведущие делали перерыв (2:03:24–2:41:21; в записи там пауза и проверка звука).
MexSet сверен с перебором на 300 массивах (границы включительные, значения вплоть до $n$ и выше).2:42:38 Те же значения, но теперь они в вершинах дерева, а запросы — на путях (2:42:38–2:42:56). Нужен эйлеров обход; чтобы получился отрезок, записываем вершину при входе и при выходе, т.е. каждую вершину два раза (2:44:18–2:45:25). Для пути $u\to v$ рассмотрим отрезок обхода между ними: вершины, лежащие на пути, встречаются в нём ровно один раз, все остальные — два (2:46:42–2:47:29).
2:47:29 Поэтому Мо работает почти без изменений: у каждой вершины заводим счётчик «сколько раз она в отрезке»; на первом вхождении добавляем её значение в структуру, на втором — удаляем (то есть переключаем) (2:48:09–2:49:04, 2:50:34–2:51:15). Для отрезка берём $[\mathrm{tin}_u,\ \mathrm{tin}_v]$, если $u$ — предок $v$, и $[\mathrm{tout}_u,\ \mathrm{tin}_v]$ иначе; во втором случае LCA в отрезок не попадает, его значение нужно добавить в структуру отдельно на время запроса (2:46:53–2:47:09, 2:51:15–2:51:40). Если значения записаны на рёбрах, записываем значение при первом и последнем проходе по ребру — тогда LCA добавлять не нужно (2:51:40–2:52:06).
// mex значений на путях дерева: Мо по эйлерову обходу длины 2n, вершины, встретившиеся дважды, «гасят» друг друга
vector<int> tree_mex(const Tree& T, const vector<int>& val, const vector<pair<int, int>>& qs) {
int n = T.n, q = qs.size();
vector<int> L(q), R(q), extra(q, -1);
for (int i = 0; i < q; i++) {
int u = qs[i].first, v = qs[i].second;
if (T.e_in[u] > T.e_in[v]) swap(u, v);
int w = T.lca(u, v);
if (w == u) { L[i] = T.e_in[u]; R[i] = T.e_in[v]; }
else { L[i] = T.e_out[u]; R[i] = T.e_in[v]; extra[i] = w; } // LCA в отрезок не попадает — добавим отдельно
}
MexSet ms(n + 1); vector<char> in(n, 0);
auto flip = [&](int pos) { int v = T.ord2[pos]; if (in[v] ^= 1) ms.add(val[v]); else ms.rem(val[v]); };
vector<int> ans(q), ord = mo_order(L, R, isqrt_ceil(2 * n));
int l = 0, r = -1;
for (int i : ord) {
while (l > L[i]) flip(--l);
while (r < R[i]) flip(++r);
while (l < L[i]) flip(l++);
while (r > R[i]) flip(r--);
if (extra[i] >= 0) ms.add(val[extra[i]]);
ans[i] = ms.mex();
if (extra[i] >= 0) ms.rem(val[extra[i]]);
}
return ans;
}2:52:15 Теперь к запросам mex добавляются изменения: «поставить в позицию $i$ новое значение». Раньше Мо опирался на то, что запросы известны заранее и нет изменений (2:52:26–2:53:04). Лектор признаётся, что Мо на олимпиадах почти не писал: однажды ему пришлось писать «Мо на дереве» на раунде Codeforces, и эту задачу он вспоминает с гордостью (2:53:39–2:54:20).
2:54:30 Запрос характеризуется тремя числами: $(l,\ r,\ t)$, где $t$ — сколько изменений применено до него. Состояние — точка в кубе. Сдвигать $l$ и $r$ мы умеем; сдвиг $t\to t+1$ тоже простой: если изменяемая позиция лежит внутри $[l,r]$, то удаляем старое значение и добавляем новое, иначе просто меняем массив; $t\to t-1$ — обратная операция (2:55:21–2:56:35).
2:56:35 Осталось выбрать порядок. Сортируем по тройке $(\lfloor l/B\rfloor,\ \lfloor r/B\rfloor,\ t)$ (2:57:23–2:57:55). Оценка: пока блоки $l$ и $r$ не меняются, $t$ растёт монотонно — не более $n$ шагов на пару блоков, а таких пар $(n/B)^2$, то есть $\frac{n^3}{B^2}$; границы $l$ внутри блока двигаются на $B$ за запрос — $nB$; $r$ в пределах блока — $nB$, а при смене блока $r$ — $\frac{n^2}{B}$ в сумме (3:00:11–3:03:52): $$O\!\left(nB+\frac{n^2}{B}+\frac{n^3}{B^2}\right).$$ При $B=n^{2/3}$ получаем $O(n^{5/3})$ (3:03:52–3:05:37). Это и называется 3D-Мо (3:05:37–3:05:44).
vector<int> mo_mex_updates(vector<int> a, const vector<Upd>& upd, const vector<array<int, 3>>& qs /* l, r, сколько изменений уже применено */) {
int n = a.size(), q = qs.size();
vector<int> oldv(upd.size()); { vector<int> b = a; for (size_t k = 0; k < upd.size(); k++) { oldv[k] = b[upd[k].pos]; b[upd[k].pos] = upd[k].val; } }
int B = max(1, (int)cbrt((double)n * n)); // блок ~ n^(2/3)
vector<int> id(q); iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int i, int j) {
const auto &x = qs[i], &y = qs[j];
if (x[0] / B != y[0] / B) return x[0] / B < y[0] / B;
if (x[1] / B != y[1] / B) return x[1] / B < y[1] / B;
return x[2] < y[2];
});
MexSet ms(n + 1); int l = 0, r = -1, t = 0; vector<int> ans(q);
auto apply = [&](int k, bool forward) {
int p = upd[k].pos, nv = forward ? upd[k].val : oldv[k], ov = forward ? oldv[k] : upd[k].val;
if (l <= p && p <= r) { ms.rem(ov); ms.add(nv); }
a[p] = nv;
};
for (int i : id) {
int L = qs[i][0], R = qs[i][1], T = qs[i][2];
while (l > L) ms.add(a[--l]);
while (r < R) ms.add(a[++r]);
while (l < L) ms.rem(a[l++]);
while (r > R) ms.rem(a[r--]);
while (t < T) apply(t++, true);
while (t > T) apply(--t, false);
ans[i] = ms.mex();
}
return ans;
}3:07:44 Для запроса $[l,r]$ нужно найти $\sum_{x<y,\ a_x=a_y}(y-x)$ — по всем парам равных элементов отрезка. Лектор признаёт, что на вид задача страшная (3:08:15–3:08:36), и снова предлагает посмотреть «в стиле Мо»: достаточно уметь расширять и сужать отрезок на один элемент (3:10:04–3:10:37).
3:10:45 Пусть справа добавляется элемент в позиции $R$, а равные ему сейчас стоят в позициях $i_1,i_2,i_3,\dots$ внутри отрезка. Тогда ответ растёт на $(R-i_1)+(R-i_2)+\dots=\mathrm{cnt}\cdot R-\sum i_j$. Нужно хранить для каждого значения только количество вхождений и сумму их индексов (3:11:03–3:11:56). Добавление слева — симметрично: прибавляется $\sum i_j-\mathrm{cnt}\cdot L$; удаление — те же формулы с вычитанием (3:11:59–3:12:50, 3:17:29–3:18:53). Значения сжимаем или храним в хеш-таблице (3:18:17–3:18:24).
vector<ll> mo_equal_pairs(vector<int> a, const vector<pair<int, int>>& qs) {
int n = a.size(), q = qs.size();
{ vector<int> s = a; sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end());
for (int& x : a) x = lower_bound(s.begin(), s.end(), x) - s.begin(); }
vector<ll> cnt(n, 0), sumIdx(n, 0), res(q); ll cur = 0;
auto add_right = [&](int p) { int v = a[p]; cur += cnt[v] * p - sumIdx[v]; cnt[v]++; sumIdx[v] += p; }; // новый индекс — самый большой
auto add_left = [&](int p) { int v = a[p]; cur += sumIdx[v] - cnt[v] * p; cnt[v]++; sumIdx[v] += p; }; // новый индекс — самый маленький
auto rem_right = [&](int p) { int v = a[p]; cnt[v]--; sumIdx[v] -= p; cur -= cnt[v] * p - sumIdx[v]; };
auto rem_left = [&](int p) { int v = a[p]; cnt[v]--; sumIdx[v] -= p; cur -= sumIdx[v] - cnt[v] * p; };
vector<int> L(q), R(q);
for (int i = 0; i < q; i++) { L[i] = qs[i].first; R[i] = qs[i].second; }
int l = 0, r = -1;
for (int i : mo_order(L, R, isqrt_ceil(n))) {
while (l > L[i]) add_left(--l);
while (r < R[i]) add_right(++r);
while (l < L[i]) rem_left(l++);
while (r > R[i]) rem_right(r--);
res[i] = cur;
}
return res;
}3:20:07 Дальше ведёт Денис, затем (с 4:06:18) блок про корневую по запросам рассказывает второй ведущий. Общая идея первой части: если у объектов выполнено какое-то суммарное ограничение, то «больших» объектов мало, и с ними можно обращаться иначе, чем с «маленькими».
3:20:25 Пусть $a_1+\dots+a_k=S$. Разобьём элементы на «не больше $\sqrt S$» и «больше $\sqrt S$». Если каждый элемент второй группы больше $\sqrt S$, а в сумме они дают не более $S$, то их не больше $\sqrt S$ (3:20:35–3:21:11). Константа $B$ вместо точного корня не важна: она одинаково входит в обе части оценки (3:23:06–3:23:23).
3:21:27 Неориентированный граф на $n$ вершинах и $m$ рёбрах; нужно число треугольников (3:21:27–3:22:13). Сумма степеней равна $2m$, поэтому вершин со степенью больше $B$ («тяжёлых») не больше $2m/B$; остальные — «лёгкие» (3:22:33–3:23:46).
3:24:09 Треугольники, где есть хотя бы одна лёгкая вершина. Перебираем вершину $v$ и по её списку смежности отмечаем её соседей (это «строка матрицы смежности», строящаяся на ходу). Перебираем лёгкого соседа $u$ и затем его соседей $w$ — их не больше $B$ — и проверяем, помечена ли $w$ (3:24:26–3:25:57). Суммарно $O(m+mB)=O(mB)$, потому что каждое ребро $vu$ рассматривается дважды (3:25:57–3:26:34).
3:27:08 Один треугольник найдётся несколько раз (зависит от числа лёгких вершин в нём), поэтому считаем $c_1,c_2,c_3$ — по числу лёгких вершин — и делим на соответствующие кратности (3:27:08–3:27:52). Треугольники из одних тяжёлых. Тяжёлых не больше $2m/B$; нумеруем их и строим матрицу смежности $\frac{2m}B\times\frac{2m}B$. Перебор всех троек — $O\!\left((m/B)^3\right)$, при $B=\sqrt m$ это $O(m\sqrt m)$ (3:28:04–3:29:32).
// (a) делим вершины на лёгкие (deg <= B) и тяжёлые; тяжёлых не больше 2m / B
ll triangles_heavy_light(int n, const vector<pair<int, int>>& edges) {
int m = edges.size(), B = isqrt_ceil(2LL * m);
vector<vector<int>> adj(n);
for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
vector<char> heavy(n); for (int v = 0; v < n; v++) heavy[v] = (int)adj[v].size() > B;
ll c[4] = {0, 0, 0, 0}; vector<char> mark(n, 0);
for (int v = 0; v < n; v++) {
for (int x : adj[v]) mark[x] = 1; // строка матрицы смежности для v
for (int u : adj[v]) if (!heavy[u]) // лёгкий сосед u: у него не больше B соседей
for (int w : adj[u]) if (mark[w]) c[!heavy[v] + !heavy[u] + !heavy[w]]++;
for (int x : adj[v]) mark[x] = 0;
}
// тройка (v; лёгкий u; w) встречается 2k раз у треугольника с k лёгкими вершинами
ll ans = c[1] / 2 + c[2] / 4 + c[3] / 6;
vector<int> hv, hid(n, -1);
for (int v = 0; v < n; v++) if (heavy[v]) { hid[v] = hv.size(); hv.push_back(v); }
int h = hv.size(); vector<vector<char>> g(h, vector<char>(h, 0));
for (auto [u, v] : edges) if (heavy[u] && heavy[v]) g[hid[u]][hid[v]] = g[hid[v]][hid[u]] = 1;
for (int i = 0; i < h; i++) for (int j = i + 1; j < h; j++) if (g[i][j])
for (int k = j + 1; k < h; k++) ans += g[i][k] && g[j][k];
return ans;
}3:29:41 Проще — ориентировать рёбра. Сортируем вершины по степени и ориентируем каждое ребро «вправо» (от меньшей степени к большей, при равных — по номеру). Утверждение: исходящая степень любой вершины $O(\sqrt m)$. Если исходная степень не больше $\sqrt m$, это очевидно. Иначе все вершины правее неё имеют степень не меньше $\sqrt m$, а таких вершин не больше $2m/\sqrt m=O(\sqrt m)$ (3:30:23–3:31:33).
3:31:38 Для вершины $u$ отмечаем её исходящих соседей, перебираем исходящее ребро $u\to v$, затем исходящие рёбра $v\to w$ и проверяем отметку $w$. Всего $O(m\sqrt m)$ (3:31:47–3:32:51).
// (b) ориентируем каждое ребро от меньшей степени к большей: исходящая степень <= sqrt(2m)
ll triangles_oriented(int n, const vector<pair<int, int>>& edges) {
vector<int> deg(n, 0); for (auto [u, v] : edges) deg[u]++, deg[v]++;
auto less_ = [&](int a, int b) { return make_pair(deg[a], a) < make_pair(deg[b], b); };
vector<vector<int>> out(n);
for (auto [u, v] : edges) { if (less_(u, v)) out[u].push_back(v); else out[v].push_back(u); }
ll ans = 0; vector<char> mark(n, 0);
for (int u = 0; u < n; u++) {
for (int v : out[u]) mark[v] = 1;
for (int v : out[u]) for (int w : out[v]) ans += mark[w];
for (int v : out[u]) mark[v] = 0;
}
return ans;
}3:33:28 Граф на $n$ вершинах и $m$ рёбрах; запросы: прибавить $x$ ко всем соседям вершины $v$ и узнать значение в вершине $u$ (3:33:42–3:34:10). В зале предлагают корневую по запросам, но лектор хочет другое решение — снова тяжёлые и лёгкие вершины (3:34:15–3:35:29).
pend и записываем $x$ в ячейку этой вершины — «отложенное» добавление (3:36:25–3:36:47, 3:38:14–3:38:49).pend[h] по всем тяжёлым $h$, соседним с $u$. Тяжёлых не больше $2m/B$, смежность проверяется по заранее построенной таблице «тяжёлая × вершина» — $\frac{m}{B}\times n$ ячеек (3:37:03–3:37:48, 3:39:04–3:40:19).struct NeighborAdd {
int n, B; vector<vector<int>> adj; vector<ll> val, pend; vector<int> hv, hid; vector<vector<char>> adjH;
NeighborAdd(int n, const vector<pair<int, int>>& edges) : n(n), adj(n), val(n, 0), hid(n, -1) {
for (auto [u, v] : edges) { adj[u].push_back(v); adj[v].push_back(u); }
B = isqrt_ceil(2LL * edges.size());
for (int v = 0; v < n; v++) if ((int)adj[v].size() > B) { hid[v] = hv.size(); hv.push_back(v); }
pend.assign(hv.size(), 0); adjH.assign(hv.size(), vector<char>(n, 0));
for (size_t h = 0; h < hv.size(); h++) for (int u : adj[hv[h]]) adjH[h][u] = 1; // матрица «тяжёлая × все»: корень × n
}
void add_neighbors(int v, ll x) {
if (hid[v] < 0) { for (int u : adj[v]) val[u] += x; } // лёгкая: пройти по <= B соседям
else pend[hid[v]] += x; // тяжёлая: только записать отложенную добавку
}
ll get(int u) { ll r = val[u]; for (size_t h = 0; h < hv.size(); h++) if (adjH[h][u]) r += pend[h]; return r; }
};3:40:47 Массив $a$; из ячейки $i$ можно прыгнуть в $i+a_i,\ i+2a_i,\ i+3a_i,\dots$ (все прыжки вправо). Нужно число различных множеств посещённых клеток (то есть число путей, начинающихся в клетке $0$; ответ по модулю) (3:40:47–3:41:26). Решение за $O(n^2)$ — динамика $dp_i$ («сколько путей приходит в клетку $i$»), в которой из $i$ прыгаем по всем $i+ka_i$; ответ — сумма $dp$ (3:41:33–3:43:22). В худшем случае (все $a_i=1$) оно квадратично.
3:43:31 Оценим работу в клетке $i$ как $\frac{n-i}{a_i}\le\frac n{a_i}$. Если $a_i\ge B$, то это $\le n/B$ — такие прыжки делаем честно, всего $O(n\cdot n/B)$ (3:44:07–3:44:48). Остаются $a_i<B$: для каждого шага $\ell<B$ и каждого остатка $r$ хранят f[ℓ][r] — сумму $dp_j$ по уже обработанным $j$ с $a_j=\ell$ и $j\bmod\ell=r$ (3:45:20–3:47:26). Клетка $i$ получает вклад от всех малых прыжков, суммируя f[ℓ][i mod ℓ] по $\ell<B$ ($O(B)$ на клетку) (3:47:26–3:48:23). Время $O(n\sqrt n)$, память $O(n)$ (f[ℓ] имеет длину ℓ) (3:48:34–3:49:16).
ll jump_paths(const vector<int>& a, ll mod) {
int n = a.size(), B = isqrt_ceil(n);
vector<ll> dp(n, 0); dp[0] = 1;
vector<vector<ll>> f(B); // f[l][r] — сумма dp[j] по j с a[j] = l, j % l = r
for (int l = 1; l < B; l++) f[l].assign(l, 0);
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int l = 1; l < B; l++) dp[i] = (dp[i] + f[l][i % l]) % mod; // малые прыжки «назад»
ans = (ans + dp[i]) % mod;
if (a[i] >= B) { for (int j = i + a[i]; j < n; j += a[i]) dp[j] = (dp[j] + dp[i]) % mod; } // большие — вперёд честно
else f[a[i]][i % a[i]] = (f[a[i]][i % a[i]] + dp[i]) % mod;
}
return ans;
}3:49:45 Строки $s_1,\dots,s_k$ суммарной длины $N$, у каждой вес $w_i$. Запросы: изменить $w_i$ и найти $\sum_{j}w_j\cdot h(s_i,s_j)$ по строкам $j$ той же длины; $h$ — число различающихся позиций (3:50:10–3:51:30). Строки разных длин друг на друга не влияют, поэтому задачи по длинам независимы (3:52:43–3:53:34). Строк длины больше $\sqrt N$ — не более $\sqrt N$ (3:53:25–3:53:34).
3:53:54 Тяжёлые (длинные) строки. Для каждой длины $L>B$ заранее считаем таблицу расстояний между всеми парами строк длины $L$. Каждый символ сравнивается не более чем с $\sqrt N$ строк, поэтому предподсчёт — $O(N\sqrt N)$ (3:54:22–3:55:14). Запрос: $\sum_j w_j\,d_{ij}$ по строкам группы, $O(\sqrt N)$; изменение веса — $O(1)$ (3:55:48–3:56:43).
3:56:55 Лёгкие (короткие) строки. Для длины $L\le B$ храним $C_{p,c}$ — сумму весов строк с символом $c$ на позиции $p$ — и $D_p=\sum_c C_{p,c}$ (3:57:13–3:58:01, 4:01:22–4:01:40). Расстояние раскладывается по позициям, и для строки $s_i$ нужно сложить по позициям вес всех строк с другим символом: $\sum_p\bigl(D_p-C_{p,s_i[p]}\bigr)$ — $O(L)=O(\sqrt N)$ (4:00:04–4:02:18). Изменение веса — пройти по символам своей строки, $O(L)$ (4:03:09–4:03:59). Итог — $O\!\left((N+Q)\sqrt N\right)$ (4:04:08–4:04:33).
3:58:12 В зале спрашивают про большой алфавит: предподсчёт $C$ требует памяти пропорционально алфавиту, и «сжимать» его нельзя. Лектор решает считать алфавит маленьким (до $26$) (3:58:44–3:58:58, 4:04:54–4:05:39).
struct HammingWeights {
vector<string> s; vector<ll> w; int B;
map<int, vector<int>> group; // длина -> номера тяжёлых строк
map<int, vector<vector<int>>> dist; // длина -> матрица попарных расстояний (только тяжёлые длины)
vector<int> pos; // номер строки внутри своей группы
map<int, vector<ll>> C, D; // лёгкие длины: C[L][p*26+c] и D[L][p]
HammingWeights(const vector<string>& str, const vector<ll>& weight) : s(str), w(weight), pos(str.size(), -1) {
ll N = 0; for (auto& x : s) N += x.size();
B = isqrt_ceil(N);
for (size_t i = 0; i < s.size(); i++) {
int L = s[i].size();
if (L > B) { pos[i] = group[L].size(); group[L].push_back(i); }
else {
if (!C.count(L)) { C[L].assign(L * 26, 0); D[L].assign(L, 0); }
for (int p = 0; p < L; p++) { C[L][p * 26 + s[i][p] - 'a'] += w[i]; D[L][p] += w[i]; }
}
}
for (auto& [L, g] : group) { // тяжёлых строк мало, так что матрица небольшая
dist[L].assign(g.size(), vector<int>(g.size(), 0));
for (size_t i = 0; i < g.size(); i++) for (size_t j = 0; j < g.size(); j++)
for (int p = 0; p < L; p++) dist[L][i][j] += s[g[i]][p] != s[g[j]][p];
}
}
void update(int i, ll nw) {
int L = s[i].size();
if (L <= B) for (int p = 0; p < L; p++) { C[L][p * 26 + s[i][p] - 'a'] += nw - w[i]; D[L][p] += nw - w[i]; }
w[i] = nw;
}
ll query(int i) {
int L = s[i].size(); ll r = 0;
if (L > B) { auto& g = group[L]; for (size_t j = 0; j < g.size(); j++) r += w[g[j]] * dist[L][pos[i]][j]; }
else for (int p = 0; p < L; p++) r += D[L][p] - C[L][p * 26 + s[i][p] - 'a'];
return r;
}
};4:06:18 Второй ведущий в оставшиеся минуты разгоняется по блоку «корневая по запросам» и предупреждает, что это будет быстро (4:06:09–4:06:27). Общий приём для оффлайна: разобьём запросы на блоки по $B$ штук; внутри блока меняется не больше $B$ объектов («плавающие»), остальное — «прибито гвоздями» и обрабатывается один раз на весь блок.
4:06:38 Граф с добавлением и удалением рёбер и запросами «лежат ли $u$ и $v$ в одной компоненте» (4:06:38–4:07:07). СНМ плохо дружит с произвольными откатами, а «трюк», который сейчас объясняется, превращает любую задачу с удалениями в задачу только с добавлениями (4:08:44–4:09:16).
vector<char> offline_connectivity(int n, const vector<ConnOp>& ops, int B) {
set<pair<int, int>> cur; vector<char> ans;
auto norm = [](int u, int v) { return make_pair(min(u, v), max(u, v)); };
vector<vector<int>> g(n); vector<int> stamp(n, -1); int cs = 0;
for (int s = 0; s < (int)ops.size(); s += B) {
int e = min((int)ops.size(), s + B);
set<pair<int, int>> touched;
for (int i = s; i < e; i++) if (ops[i].type != 2) touched.insert(norm(ops[i].u, ops[i].v));
DSU d(n);
for (auto& ed : cur) if (!touched.count(ed)) d.unite(ed.first, ed.second); // «прибитые гвоздями» рёбра
vector<int> comp(n); for (int v = 0; v < n; v++) comp[v] = d.find(v);
vector<pair<int, int>> fl; // плавающие рёбра, живые сейчас
for (auto& ed : touched) if (cur.count(ed)) fl.push_back(ed);
for (int i = s; i < e; i++) {
auto ed = norm(ops[i].u, ops[i].v);
if (ops[i].type == 0) { cur.insert(ed); fl.push_back(ed); }
else if (ops[i].type == 1) { cur.erase(ed); fl.erase(find(fl.begin(), fl.end(), ed)); }
else {
for (auto& f : fl) { int a = comp[f.first], b = comp[f.second]; g[a].push_back(b); g[b].push_back(a); }
int src = comp[ops[i].u], dst = comp[ops[i].v]; cs++;
vector<int> st{src}; stamp[src] = cs;
while (!st.empty()) { int x = st.back(); st.pop_back(); for (int y : g[x]) if (stamp[y] != cs) { stamp[y] = cs; st.push_back(y); } }
ans.push_back(stamp[dst] == cs);
for (auto& f : fl) { g[comp[f.first]].clear(); g[comp[f.second]].clear(); }
}
}
}
return ans;
}4:25:54 Таблица $n\times m$ ($nm$ порядка $10^6$), все клетки белые; запросы: покрасить клетку в чёрный и найти манхэттенское расстояние от клетки до ближайшей чёрной (4:26:01–4:26:31). Условие можно усложнить: чёрные клетки снова становятся белыми — приём тот же (4:27:50–4:28:26, 4:31:52–4:32:20).
4:27:24 Бьём запросы на блоки по $B$. В блоке клетки, меняющие цвет, — «плавающие» (не более $B$ штук), остальные чёрные клетки в этом блоке неизменно чёрные. Запускаем мультиBFS (в очереди сразу все постоянно чёрные клетки, расстояние нуль) за $O(nm)$ (4:29:20–4:30:19). Запрос: берём значение BFS и просматриваем в лоб плавающие клетки, живые (чёрные) в данный момент, считая $|x_1-x_2|+|y_1-y_2|$ (4:30:32–4:31:18). Время $O\!\left(\frac QB\,nm+QB\right)$; значение $B$ подбирается из равенства (4:31:18–4:31:52).
// тип 0 — покрасить в чёрный, 1 — вернуть белый, 2 — спросить; -1, если чёрных клеток нет
vector<int> grid_nearest(int n, int m, const vector<array<int, 3>>& ops, int B) {
vector<char> black(n * m, 0); vector<int> ans; const int INF = 1e9;
for (int s = 0; s < (int)ops.size(); s += B) {
int e = min((int)ops.size(), s + B);
vector<char> touched(n * m, 0); vector<int> cells;
for (int i = s; i < e; i++) if (ops[i][0] != 2) { int c = ops[i][1] * m + ops[i][2]; if (!touched[c]) { touched[c] = 1; cells.push_back(c); } }
vector<int> dist(n * m, INF); queue<int> q;
for (int c = 0; c < n * m; c++) if (black[c] && !touched[c]) { dist[c] = 0; q.push(c); } // мультиBFS из «прибитых» чёрных
while (!q.empty()) {
int c = q.front(); q.pop(); int x = c / m, y = c % m;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
for (int k = 0; k < 4; k++) {
int nx = x + dx[k], ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || dist[nx * m + ny] != INF) continue;
dist[nx * m + ny] = dist[c] + 1; q.push(nx * m + ny);
}
}
for (int i = s; i < e; i++) {
int c = ops[i][1] * m + ops[i][2];
if (ops[i][0] == 0) black[c] = 1;
else if (ops[i][0] == 1) black[c] = 0;
else {
int best = dist[c];
for (int f : cells) if (black[f]) best = min(best, abs(f / m - ops[i][1]) + abs(f % m - ops[i][2])); // плавающие — в лоб
ans.push_back(best >= INF ? -1 : best);
}
}
}
return ans;
}4:34:28 Рёбра добавляются и удаляются, нужен вес остова после запроса (4:34:28–4:34:41). Лектор предупреждает: «задача скорее идейная — про устройство остовов, а не про корневую» (4:36:26–4:36:41). Блок запросов длины $B$; рёбра, меняющиеся в блоке, — плавающие (множество $D$, $|D|\le B$); остальные живые рёбра — множество $E$, они живы на всём блоке (4:36:45–4:38:03).
4:46:04 Почему этого достаточно: минимальный остов при добавлении ребра меняется лишь заменой наибольшего ребра на цикле (свойство «минимакс на пути»); мысленно добавляя плавающие рёбра по одному, мы получаем настоящий остов, уже лежащий в выбранных рёбрах (4:46:35–4:48:50).
4:49:53 Предподсчёт блока — Краскал по $O(Q)$ рёбрам, $O(Q\log Q)$; блоков $Q/B$. Итого $O\!\left(\frac QB\,Q\log Q+QB\log B\right)$, при $B=\sqrt Q$ — $O(Q\sqrt Q\log Q)$ (4:49:53–4:50:31). Замена СНМ перебором «за $B$» дала бы $B^3$ на запрос и была бы хуже (4:50:44–4:51:51).
vector<ll> offline_mst(int n, const vector<MstOp>& ops, int B) {
map<int, MEdge> cur; vector<ll> ans;
auto cmp = [](const MEdge& a, const MEdge& b) { return make_pair(a.w, a.id) < make_pair(b.w, b.id); };
for (int s = 0; s < (int)ops.size(); s += B) {
int e = min((int)ops.size(), s + B);
set<int> touched; vector<MEdge> all;
for (auto& kv : cur) all.push_back(kv.second);
for (int i = s; i < e; i++) if (ops[i].type != 2) {
touched.insert(ops[i].id);
if (ops[i].type == 0) all.push_back({ops[i].id, ops[i].u, ops[i].v, ops[i].w});
}
sort(all.begin(), all.end(), cmp);
// шаг А: остов на всех рёбрах, живых хоть когда-то в блоке; неплавающие рёбра остова лежат в остове всегда
DSU d(n); vector<MEdge> forced; ll wForced = 0; int comps = n;
for (auto& ed : all) if (d.unite(ed.u, ed.v)) { comps--; if (!touched.count(ed.id)) { forced.push_back(ed); wForced += ed.w; } }
bool spanning = comps == 1;
vector<MEdge> cand; vector<int> cid(n); int C = 0;
if (spanning) {
DSU d2(n); for (auto& ed : forced) d2.unite(ed.u, ed.v); // сжимаем граф по ним
vector<int> label(n, -1);
for (int v = 0; v < n; v++) { int r = d2.find(v); if (label[r] < 0) label[r] = C++; cid[v] = label[r]; }
// шаг Б: из остальных неплавающих рёбер оставляем только те, что нужны остову сжатого графа
DSU d3(C);
for (auto& ed : all) if (!touched.count(ed.id) && d3.unite(cid[ed.u], cid[ed.v])) cand.push_back(ed);
}
set<int> alive; // плавающие рёбра, живые прямо сейчас
for (int id : touched) if (cur.count(id)) alive.insert(id);
map<int, MEdge> fl; for (int i = s; i < e; i++) if (ops[i].type == 0) fl[ops[i].id] = {ops[i].id, ops[i].u, ops[i].v, ops[i].w};
for (int id : alive) fl[id] = cur[id];
for (int i = s; i < e; i++) {
if (ops[i].type == 0) { cur[ops[i].id] = fl[ops[i].id]; alive.insert(ops[i].id); }
else if (ops[i].type == 1) { cur.erase(ops[i].id); alive.erase(ops[i].id); }
else {
if (!spanning) { ans.push_back(-1); continue; }
vector<MEdge> es = cand; for (int id : alive) es.push_back(fl[id]);
sort(es.begin(), es.end(), cmp); // не больше 2B рёбер на запрос
DSU dq(C); ll tot = wForced; int cc = C;
for (auto& ed : es) if (dq.unite(cid[ed.u], cid[ed.v])) { tot += ed.w; cc--; }
ans.push_back(cc == 1 ? tot : -1);
}
}
}
return ans;
}4:52:24 Последний приём, «с которым на олимпиадах встречались три раза»: перебрать все различные значения вида $\lfloor x/i\rfloor$, $i=1,2,\dots$ (4:52:24–4:53:20). Различных значений не больше $2\sqrt x$: при $i\le\sqrt x$ — не более $\sqrt x$ значений, при $i>\sqrt x$ значение меньше $\sqrt x$ (4:54:31–4:54:54).
4:55:08 Идём по возрастанию $i$ и ищем минимальное $j>i$, у которого значение меньше: если $k=\lfloor x/i\rfloor$, то условие $\lfloor x/j\rfloor<k$ равносильно $x/j<k$ (округление можно снять), то есть $j>x/k$. Наименьшее такое целое $j$ — это $\lfloor x/k\rfloor+1$ (4:55:48–4:58:21). Цикл: for (i = 1; i <= x; i = x / (x / i) + 1). Если округление вверх — упражнение (4:52:50–4:53:05).
vector<array<ll, 3>> floor_blocks(ll x) { // {значение k, i от, i до}
vector<array<ll, 3>> r;
for (ll i = 1; i <= x;) { ll k = x / i, j = x / k; r.push_back({k, i, j}); i = j + 1; } // следующий i — это x/k + 1
return r;
}