0:09 План занятия: персистентность, offline dynamic connectivity (ДЦП), разбор задач на эти темы, дерево Ли Чао, Kinetic Segment Tree и «китайское» дерево отрезков (Segment Tree Beats) с историческими суммами. Персистентной называется структура данных, к которой можно делать запросы и при этом обращаться к её старым версиям.
0:51 Персистентное ДО — это обычное неявное дерево отрезков (вершины созданы по мере необходимости, у каждой вершины хранятся указатели на детей). При изменении (например, «+= x в точке») мы спускаемся по пути от корня к листу и копируем все вершины на этом пути; остальные вершины остаются общими со старой версией. Новая версия — это новый корень. Каждая версия стоит $O(\log n)$ памяти и времени.
3:37 Пока операция — «изменить точку», всё просто. С массовыми операциями приходится хранить отложенные модификаторы и делать push. Наивный подход: стоим в вершине $v$, перед спуском делаем $v:=\mathrm{copy}(v)$, затем push(v), который обязан скопировать и обоих детей (мы меняем в них модификатор). Получается по три новых вершины на каждый уровень — это съедает бесконечно много памяти.
5:38 Оптимизация: заметим, что после push дети уже скопированы, поэтому, если мы спустились в одного из них, его не нужно копировать второй раз. Достаточно один раз скопировать корень, а во всех рекурсивных вызовах считать, что переданная вершина уже «наша» (можно менять). Тогда на уровень получается лишь две новые вершины.
6:18 Ещё сильнее, если модификатор лёгкий (например, одно число): хранить в вершине отдельный модификатор для левого и для правого ребёнка. Почти всегда отрезок запроса в вершине — префикс или суффикс её отрезка. Если он задевает только правого сына, то мы просто обновляем «правый» модификатор и спускаемся в правого (левого не копируем и не трогаем); если задевает обоих — обновляем правый модификатор, а левого копируем, пушим в него и спускаемся. Итого одно копирование на уровень. В задачах с персистентной неявной ДО и персистентным декартовым деревом именно память чаще всего оказывается узким местом.
8:21 В обычном декартовом дереве у вершины есть приоритет $y$, и при слиянии корнем становится вершина с минимальным приоритетом. В персистентном декартовом дереве приоритеты хранить нельзя: при merge двух деревьев мы запускаем случайность и выбираем корень с вероятностью, пропорциональной размеру дерева, а затем сливаем его ребёнка с другим деревом. Для анализа нужно, чтобы каждая вершина с равной вероятностью была корнем своего поддерева; выбор пропорционально размерам даёт именно это.
9:45 Проблема: самослияние. Если по операциям декартово дерево может сливаться с самим собой (в том числе с копией), оценка $O(\log n)$ ломается. Пример худшего случая: слили дерево с самим собой дважды, обрезали до $10^9$ элементов, снова слили с собой, обрезали — и так далее. Ожидание «каждая операция за $\log$ от размера» не выполняется: нарушается независимость событий «вершина — корень поддерева», так как одна и та же вершина оказывается в нескольких поддеревьях. Если же в каждом дереве каждая вершина встречается ровно один раз (например, мы лишь добавляем элементы в новые версии), всё в порядке.
13:13 Поэтому для задач с самослиянием берут сбалансированные деревья с гарантированной (не амортизированной) оценкой: красно-чёрное, 2–3-дерево. Splay не подходит — его оценка амортизированная. Лектор отмечает, что 2–3-деревья умеют сливаться за разность высот, и в них самослияние $N$ раз не вырождается; как их писать, расскажут во втором полугодии.
15:57 В граф добавляются и удаляются рёбра; в каждый момент времени нужно ответить на вопрос (например, связен ли граф или сколько в нём компонент). Если запросы известны заранее (offline), то:
17:19 Откат в СНМ возможен, если не использовать сжатие путей: объединяем по размеру (или рангу) и храним историю слияний. Каждый добавленный/удалённый вызов — $O(\log n)$, всего $O(m\log T\log n)$.
// СНМ с откатами: union по размеру, без сжатия путей, поэтому операцию можно отменить
struct RollbackDSU {
vector<int> p, sz;
vector<pair<int,int>> hist; // (корень-родитель, присоединённый корень)
int comps;
RollbackDSU(int n) : p(n), sz(n, 1), comps(n) { iota(p.begin(), p.end(), 0); }
int find(int v) { while (p[v] != v) v = p[v]; return v; }
void unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
p[b] = a; sz[a] += sz[b]; comps--;
hist.push_back({a, b});
}
void rollback(size_t label) { // откатиться до размера истории label
while (hist.size() > label) {
auto [a, b] = hist.back(); hist.pop_back();
sz[a] -= sz[b]; p[b] = b; comps++;
}
}
};
// Offline dynamic connectivity: ребро живёт на полуинтервале времени [l, r)
struct OfflineDCP {
int T;
vector<vector<pair<int,int>>> tree; // рёбра, лежащие в вершинах дерева отрезков по времени
RollbackDSU dsu;
vector<int> ans; // ans[t] — число компонент в момент t
OfflineDCP(int n, int T) : T(T), tree(4 * T), dsu(n), ans(T) {}
void addEdge(int u, int v, int l, int r) { add(1, 0, T, l, r, {u, v}); }
void add(int v, int tl, int tr, int l, int r, pair<int,int> e) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { tree[v].push_back(e); return; }
int m = (tl + tr) / 2;
add(2 * v, tl, m, l, r, e); add(2 * v + 1, m, tr, l, r, e);
}
void run() { dfs(1, 0, T); }
void dfs(int v, int tl, int tr) {
size_t label = dsu.hist.size(); // запоминаем, докуда откатываться
for (auto [a, b] : tree[v]) dsu.unite(a, b);
if (tr - tl == 1) ans[tl] = dsu.comps;
else { int m = (tl + tr) / 2; dfs(2 * v, tl, m); dfs(2 * v + 1, m, tr); }
dsu.rollback(label); // не забыть откат на выходе — в том числе в листе!
}
};17:59 Удобная реализация откатов. Запоминаем при входе в вершину размер вектора истории (label = dsu.hist.size()), а на выходе просим «откатись до этого размера». Главная ошибка — забыть откатить в каком-то случае; лектор отмечает, что чаще всего забывает откат в листе.
19:20 Эту же идею можно писать без явного дерева, как «разделяй и властвуй»: функция принимает отрезок времени и список отрезков существования рёбер. Делим время пополам; налево передаём отрезки, пересекающиеся с левой половиной, направо — с правой; отрезки, которые целиком накрывают текущий отрезок времени, добавляем в СНМ и дальше не передаём. Иногда это понятнее, чем явное ДО.
21:23 Трюк для сложного отката. Если откатывать приходится много массивов (предки, ранги, размеры…), можно завести один общий вектор «откатов» из пар (указатель на ячейку, старое значение) и менять значения только через функцию set(ячейка, новое), которая сохраняет в него пару. Откат — цикл, который восстанавливает значения по указателям, пока размер вектора больше метки. Это удобнее, чем откатывать каждый массив по индексам, но чуть медленнее (хранятся указатели). Лектор отмечает, что это не так оптимально, как откатывать каждый массив руками по индексам (хранятся указатели), но писать удобнее.
23:25 ДЦП за $O(\log)$ (вместо $\log^2$) — это идея из диплома Сергея Каплёвича. Возьмём ту же «разделяйку» по времени. В вершине-отрезке времени мы знаем:
27:32 При спуске в ребёнка часть синих рёбер становится красными (они полностью накрывают отрезок ребёнка), часть выбрасывается (не пересекают его). Нужно построить граф на красных компонентах с этими новыми красными рёбрами, стянуть его компоненты и пересчитать для оставшихся синих рёбер номера компонент (DFS по небольшому графу компонент). Код сложнее, чем с откатами, но работает заметно быстрее — и это не «мега», а «получше».
28:55 Пусть у рёбер есть вес, а нужно в каждый момент времени знать вес минимального остова. Та же схема: в вершине-отрезке времени строим остов только на красных рёбрах и остов на красных и синих. Затем для каждого красного ребра:
31:38 Так динамический остов решается за $O(\log^2)$ — той же техникой можно получить и $O(\log)$. Общая идея полезна: если есть много объектов, живущих на отрезках, смотрим «всё без отрезка» и «всё с отрезком» и фиксируем то, что оказалось в обоих случаях.
Здесь — идеи решений, как их рассказывал лектор (часть условий восстановлена по записи; код без пометки не приводится — только где он проверялся).
34:25 Дан массив и запросы $[l,r)$: найти наименьшее число, которое встречается на отрезке нечётное число раз. Для префиксов всё просто: храним в ДО по сжатым значениям чётность количества вхождений каждого значения и спускаемся влево, если слева есть единица. Для отрезков берём персистентное ДО по префиксам и сравниваем версии $r$ и $l$:
38:32 Хэш — это xor случайных 64-битных чисел для значений, поэтому решение вероятностное. Чтобы избавиться от случайности, можно заводить уникальные номера для пар «хэш левого, хэш правого», но это дорого по памяти и времени; лектор считает вариант с одним long long достаточным.
// Наименьшее число, встречающееся нечётное число раз на a[l..r). Версии = префиксы; в вершине — xor случайных хэшей.
struct OddMin {
int m; // число различных значений после сжатия
vector<ll> rnd, hs; vector<int> L, R;
vector<int> roots, vals;
int newNode(int l, int r, ll h) { L.push_back(l); R.push_back(r); hs.push_back(h); return (int)L.size() - 1; }
int toggle(int v, int tl, int tr, int pos) {
if (tr - tl == 1) return newNode(0, 0, hs[v] ^ rnd[pos]);
int mid = (tl + tr) / 2, l = L[v], r = R[v];
if (pos < mid) l = toggle(L[v], tl, mid, pos); else r = toggle(R[v], mid, tr, pos);
return newNode(l, r, hs[l] ^ hs[r]);
}
OddMin(const vector<int>& a) {
vals = a; sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end());
m = vals.size();
mt19937_64 gen(712367);
rnd.resize(m); for (auto& x : rnd) x = gen();
newNode(0, 0, 0); // пустое дерево
roots.push_back(0);
for (int x : a) {
int pos = lower_bound(vals.begin(), vals.end(), x) - vals.begin();
roots.push_back(toggle(roots.back(), 0, m, pos));
}
}
int query(int l, int r) { // -1, если нечётных нет
int u = roots[r], v = roots[l], tl = 0, tr = m;
if (hs[u] == hs[v]) return -1;
while (tr - tl > 1) {
int mid = (tl + tr) / 2;
if (hs[L[u]] != hs[L[v]]) { u = L[u]; v = L[v]; tr = mid; } // различие слева — идём налево
else { u = R[u]; v = R[v]; tl = mid; }
}
return vals[tl];
}
};Проверка. Код сравнивался с перебором на всех отрезках случайных массивов; расхождений не было.
39:56 Для каждого $k=1..n$ найти минимальное число отрезков, на которые можно разбить массив так, что в каждом не больше $k$ различных чисел.
// Персистентное ДО по версиям l = n-1..0: в версии l единица стоит на первом вхождении каждого значения в суффиксе [l, n).
// Тогда сумма на [l, r) в версии l = число различных на a[l..r).
struct PersistentSeg {
vector<int> L, R, sum;
int n;
int newNode(int l, int r, int s) { L.push_back(l); R.push_back(r); sum.push_back(s); return (int)L.size() - 1; }
PersistentSeg(int n) : n(n) { newNode(0, 0, 0); } // узел 0 — «пустое» дерево из нулей
int upd(int v, int tl, int tr, int pos, int d) { // новая версия: a[pos] += d
int s = sum[v] + d;
if (tr - tl == 1) return newNode(0, 0, s);
int m = (tl + tr) / 2, l = L[v], r = R[v];
if (pos < m) l = upd(L[v], tl, m, pos, d); else r = upd(R[v], m, tr, pos, d);
return newNode(l, r, s);
}
int firstExceed(int v, int tl, int tr, int k) { // минимальная позиция p, что сумма на [0..p] > k, иначе n
if (sum[v] <= k) return n;
if (tr - tl == 1) return tl;
int m = (tl + tr) / 2;
if (sum[L[v]] > k) return firstExceed(L[v], tl, m, k);
return firstExceed(R[v], m, tr, k - sum[L[v]]);
}
};
// ответ для каждого k: минимальное число отрезков, на которые можно разбить массив так, чтобы в каждом было <= k различных
vector<int> minPartsForAllK(const vector<int>& a) {
int n = a.size();
PersistentSeg st(n);
vector<int> root(n + 1, 0);
map<int,int> nxt; // следующее вхождение значения справа
for (int l = n - 1; l >= 0; l--) {
int r = root[l + 1];
r = st.upd(r, 0, n, l, +1);
if (nxt.count(a[l])) r = st.upd(r, 0, n, nxt[a[l]], -1);
nxt[a[l]] = l; root[l] = r;
}
vector<int> res(n + 1, 0);
for (int k = 1; k <= n; k++) {
int pos = 0, cnt = 0;
while (pos < n) { pos = st.firstExceed(root[pos], 0, n, k); cnt++; } // жадно берём самый длинный отрезок
res[k] = cnt;
}
return res;
}Проверка. Результат minPartsForAllK сравнивался с честным жадным перебором для всех $k$ на случайных массивах; расхождений не найдено.
44:46 Есть $n$ тортиков, у каждого цена $c_i$ и вкусность $t_i$. Покупатель идёт по тортикам по порядку и покупает очередной, если на него хватает денег. Для множества запросов «у меня $C$ денег» найти суммарную вкусность купленного.
55:09 Идея без кода. Реализация не проверялась.
56:36 Запросы: найти НОК на отрезке (в условии по записи — по простому модулю). Идея: перебираем правую границу $r$ и храним персистентное ДО по левой границе, в котором в позиции $l$ записан ответ на $[l,r]$.
Идея без кода.
62:02 Дан ациклический ориентированный граф, на рёбрах — буквы (из одной вершины рёбра с разными буквами). Нужно для разных $k$ найти $k$-й в лексикографическом порядке путь из вершины 1 в $N$ (в записи условие дано неполно — речь идёт о длине такого пути). Решение: в каждой вершине хранить персистентное 2–3-дерево (или декартово), где в $k$-й позиции лежит длина $k$-го лексикографически пути из неё в $N$, обрезанное по $10^9$. Пересчёт: смотрим на соседей в порядке букв, берём дерево соседа, прибавляем к нему единицу и сливаем с предыдущим; в конце обрезаем (лучше сразу, не добавляя то, что всё равно обрежется). 64:06 Именно здесь нужна структура, которая умеет «сама с собой сливаться» — декартово дерево будет работать долго, 2–3-дерево быстро. Вариант «$k$-й символ пути» требует хранить в деревьях строки (дерево с «припиской символа» как модификатор); лектор считает такое решение излишне сложным на практике.
70:08 Дана куча отрезков. Из отрезка $i$ можно перейти в $j$, если $i$ вложен в $j$ и не существует отрезка $k$, вложенного в $j$ и содержащего $i$ («разлучника»). Для каждого $i$ нужно найти число путей из него.
Идея без кода.
81:12 Неориентированный взвешенный граф; вес каждого ребра — степень двойки $2^{k_i}$, где $k_i$ может быть до $10^5$. Нужно найти расстояние от 1 до $N$. Обычная Дейкстра работает, но расстояния — это битовые строки длины порядка $10^5$.
Идея без кода.
90:05 Дан плоский граф (уже нарисован на плоскости, все грани пронумерованы, граф не меняется). Для каждой точки запроса найти грань, которой она принадлежит (либо отрезок на границе двух граней).
set держим отрезки, пересекающие прямую, отсортированные по координате пересечения.98:57 Задачи 9 («добавить ребро, посчитать число мостов») и 10 («$k$-я порядковая статистика различных на отрезке») на занятии пропустили.
99:37 Блок начинается с оптимизации динамики выпуклой оболочкой прямых (CHT); в записи эта часть про монотонные наклоны не сохранилась — продолжение начинается с случая произвольных наклонов. Дерево Ли Чао (Li Chao tree, ЛЧ) поддерживает произвольный порядок добавления прямых $y=kx+b$ и запрос «минимум по всем прямым в точке $x$».
101:09 Пусть все точки $x_1<\dots<x_n$, в которых будут запросы, известны. Строим ДО по ним и в каждой вершине храним одну прямую. 101:49 Инвариант: для любой точки $x$ минимум по всем добавленным прямым равен минимуму значений прямых, лежащих в вершинах на пути от листа $x$ до корня. Пустая структура: во всех вершинах «прямая» с $b=+\infty$ (или $-\infty$ для максимума).
103:53 Как добавить новую прямую. Пусть $x_m$ — середина отрезка вершины.
108:43 Корректность следует из того, что в поддерево, куда мы не спускаем проигравшую прямую, она никогда не нужна: там она хуже прямой в вершине. Одна вставка — $O(\log n)$, запрос (минимум по пути) — $O(\log n)$.
109:25 По сравнению с CHT (где нет структуры ДО и дополнительной памяти) Ли Чао хуже по константе и памяти (порядка $4n$ вершин), но не требует монотонности наклонов и поддерживает более сложные запросы.
110:06 Пусть прямая действует лишь на отрезке $[x_L,x_R]$. Разбиваем этот отрезок на $O(\log n)$ вершин ДО и в каждую вставляем прямую тем же рекурсивным алгоритмом. 113:10 Инвариант сохраняется: прямые, не пересекающие отрезок запроса, не затрагиваются, а внутри каждой вершины разбиения вставка корректна для её поддерева. Время — $O(\log^2n)$ на вставку ($\log$ от разбиения и $\log$ от вставки в каждую вершину). 115:15 Дерево можно создавать неявно: несуществующие вершины просто появляются при первой вставке.
// Дерево Ли Чао на минимум. Абсциссы xs известны заранее; прямая может действовать только на отрезке индексов [l, r).
struct Line {
ll k, b;
ll eval(ll x) const { return k * x + b; }
};
const Line NONE = {0, (ll)4e18}; // «бесконечно высокая» прямая
struct LiChao {
int n;
vector<ll> xs;
vector<Line> t;
LiChao(vector<ll> xs_) : n(xs_.size()), xs(xs_), t(4 * xs_.size(), NONE) {}
// добавить прямую во всё поддерево вершины v (отрезок индексов [tl, tr))
void insert(int v, int tl, int tr, Line nw) {
int m = (tl + tr) / 2;
if (nw.eval(xs[m]) < t[v].eval(xs[m])) swap(nw, t[v]); // в середине в вершине лежит лучшая из двух
if (tr - tl == 1) return; // в листе хватает одной прямой
// nw в точке xs[m] хуже; она может быть лучше только с одной стороны
if (nw.eval(xs[tl]) < t[v].eval(xs[tl])) insert(2 * v, tl, m, nw); // слева лучше
else if (nw.eval(xs[tr - 1]) < t[v].eval(xs[tr - 1])) insert(2 * v + 1, m, tr, nw); // справа лучше
// иначе nw нигде не лучше t[v] — выбрасываем
}
// добавить прямую только на отрезок индексов [l, r): разбиваем на O(log n) вершин и в каждую вставляем
void insertSeg(int v, int tl, int tr, int l, int r, Line nw) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { insert(v, tl, tr, nw); return; }
int m = (tl + tr) / 2;
insertSeg(2 * v, tl, m, l, r, nw); insertSeg(2 * v + 1, m, tr, l, r, nw);
}
ll query(int v, int tl, int tr, int i) { // минимум по прямым на пути до корня
ll res = t[v].eval(xs[i]);
if (tr - tl == 1) return res;
int m = (tl + tr) / 2;
return min(res, i < m ? query(2 * v, tl, m, i) : query(2 * v + 1, m, tr, i));
}
};Проверка. Код сравнивался с перебором на случайных наборах прямых (в том числе на отрезках) и запросах; расхождений не было.
116:38 Запрос теперь: $(x,K)$, где $K\le 20$ — найти $K$-е по величине значение среди прямых в точке $x$. 118:05 Хранить будем до $2K-1$ прямых в каждой вершине, а инвариант: $K$-й минимум в точке лежит среди прямых вершин на пути до корня.
119:27 Когда прямых стало больше $2K-1$, сортируем их по значению в $x_m$ и оставляем $2K-1$ самых низких; самую высокую $\ell_0$ нужно «отправить» вниз. Разобьём остальные $2K-1$ прямых на две группы: наклон $\le k_0$ и наклон $>k_0$. 120:47 Прямая с меньшим наклоном и меньшим значением в $x_m$ правее $x_m$ ниже $\ell_0$ везде; с большим — левее. 122:12 Так как групп две, а всего $2K-1$ прямых, одна из них содержит не менее $K$ прямых. Если это группа с меньшим наклоном — справа $\ell_0$ не попадёт в топ-$K$, значит она нужна только слева, и мы спускаем её в левого ребёнка; иначе — в правого.
Исправление. В записи лектор говорит, что при большой первой группе нужно «спуститься вправо». Это оговорка: если не менее $K$ прямых лучше $\ell_0$ правее $x_m$, то справа $\ell_0$ не нужна, и спускать её надо влево (так и сделано в коде ниже).
122:52 Время: $O(K)$ работы на каждой вершине пути (найти максимум и посчитать группы), итого $O(K\log n)$ на вставку и на запрос (запрос — собрать прямые на пути и взять $K$-ю по величине через nth_element). 124:14 Если прямые ещё и ограничены отрезками $[L,R)$, снова разбиваем отрезок на $O(\log n)$ вершин и вставляем в каждую — получаются «дикие» запросы, а код почти тот же.
// Ли Чао для «K-й минимум в точке по множеству прямых», K небольшое. В каждой вершине хранится не более 2K-1 прямых.
struct LiChaoK {
int n, K;
vector<ll> xs;
vector<vector<Line>> t;
LiChaoK(vector<ll> xs_, int K) : n(xs_.size()), K(K), xs(xs_), t(4 * xs_.size()) {}
void insert(int v, int tl, int tr, Line nw) {
t[v].push_back(nw);
if ((int)t[v].size() <= 2 * K - 1) return; // место ещё есть
int m = (tl + tr) / 2; ll xm = xs[m];
// самая высокая в точке xm прямая ext — кандидат на вылет из вершины
int hi = 0;
for (int i = 1; i < (int)t[v].size(); i++) if (t[v][i].eval(xm) > t[v][hi].eval(xm)) hi = i;
Line ext = t[v][hi]; swap(t[v][hi], t[v].back()); t[v].pop_back();
if (tr - tl == 1) return; // лист: x единственный, лишняя прямая не нужна
// среди оставшихся 2K-1 прямых считаем те, что имеют наклон не больше, чем у ext (и ниже её в xm):
// правее xm такие прямые лучше ext везде
int cntLessOrEq = 0;
for (auto& l : t[v]) if (l.k <= ext.k) cntLessOrEq++;
if (cntLessOrEq >= K) insert(2 * v, tl, m, ext); // справа ext не попадёт в топ-K -> идём влево
else insert(2 * v + 1, m, tr, ext); // иначе >= K прямых с большим наклоном: слева она хуже -> вправо
}
ll query(int i) { // K-е по величине значение; INF, если прямых меньше K
vector<ll> vals;
int v = 1, tl = 0, tr = n;
while (true) {
for (auto& l : t[v]) vals.push_back(l.eval(xs[i]));
if (tr - tl == 1) break;
int m = (tl + tr) / 2;
if (i < m) { v = 2 * v; tr = m; } else { v = 2 * v + 1; tl = m; }
}
if ((int)vals.size() < K) return (ll)4e18;
nth_element(vals.begin(), vals.begin() + K - 1, vals.end());
return vals[K - 1];
}
};Проверка. $K=1..4$, случайные прямые, значения запросов сверялись с сортировкой всех прямых; расхождений не было.
125:00 Если $x$ заранее неизвестны, ДО строят на всех вещественных точках сразу и спускаются только до глубины, нужной для точности $\varepsilon$: вместо запроса в $x$ делают запрос в $x+\varepsilon$ — ответ сильно не меняется.
127:02 CHT и Ли Чао добавляют прямые и ищут минимум в точке. Kinetic segment tree (KST) — другая концепция: прямые уже заданы и пронумерованы, это массив $(k_i,b_i)$. Есть глобальная координата $x$ (изначально $-\infty$). Запросы: минимум по отрезку номеров прямых при текущем $x$, и увеличить $x$ на $\Delta>0$. 128:24 Можно сделать это через ДО с CHT в каждой вершине (запрос $O(\log^2n)$ или амортизированно $O(\log n)$ с указателями), но KST позволяет ещё и менять прямые.
131:11 Идея: в каждой вершине ДО хранить текущую оптимальную прямую в текущем $x$ — просто сравнивая прямые детей в точке $x$. Ответ на запрос — разложение отрезка на $O(\log n)$ вершин и минимум их значений. 132:33 Что происходит при увеличении $x$: в вершине может сменить победитель (пересеклись прямые детей). Поэтому дополнительно храним melting point — максимальный сдвиг $x$, при котором ничего во всём поддереве не меняется. Для вершины $v$ с детьми $L,R$: $$\mathrm{melt}(v)=\min\bigl(\mathrm{melt}(L),\ \mathrm{melt}(R),\ x^*-x\bigr),$$ где $x^*$ — точка пересечения прямых-победителей детей (если победитель левого ребёнка растёт быстрее; иначе $\infty$).
135:20 Функция update(v, Δ): если $\mathrm{melt}(v)\ge\Delta$ — просто уменьшаем melt, обновляем значение победителя, прибавляем $\Delta$ в отложенный модификатор и возвращаемся; иначе рекурсивно вызываем её от обоих детей и пересчитываем $v$.
136:43 Время без замены прямых. Каждое срабатывание melting point — это ровно сдвиг указателя в CHT вершины, всего таких событий $O(n\log n)$, к каждому нужно спуститься $O(\log n)$: итого $O(n\log^2n)$. 138:06 При замене прямых CHT уже неприменим, а оценка выходит порядка $O(n\log^2n\cdot\alpha)$: «прямую, существовавшую на отрезке времени», можно рассматривать как функцию, пересекающуюся с другими не более чем в двух точках. Размер нижней огибающей таких функций ограничивается величиной $n\alpha(n)$ (здесь $\alpha$ — обратная функция Аккермана); для функций с $s$ пересечениями оценка растёт, но остаётся почти линейной.
Важное дополнение. Строго: нижняя огибающая $n$ непрерывных функций, любые две из которых пересекаются не более $s$ раз, имеет сложность $\lambda_s(n)$ (последовательности Davenport–Schinzel); для отрезков на прямой это $\lambda_3(n)=\Theta(n\alpha(n))$. Лектор доказательства не приводит и отмечает, что на практике всё это не встречал.
142:12 Теперь у каждой прямой своя точка $x_i$. Операции:
144:15 Оценка (лектор называет её «теоретической»): порядка $n\log^2n$ на начальное построение и $Q\log^3n$ на запросы; на практике работает намного быстрее — тест, на котором она достигается, придумать очень сложно.
145:36 Что хранить в вершине. Вместо «сколько осталось до события» хранить удобнее момент события и текущий момент времени (то есть melt и накопленный отложенный модификатор), чтобы не обновлять число на всём поддереве. В вершине: победитель (наклон и значение), melt, отложенный сдвиг $x$ (модификатор «увеличить $x$»), отложенный «$+=$ к $b$». 148:17 Функция apply применяет к вершине два модификатора; если сдвиг $x$ превысил melt, она рекурсивно спускается и пересчитывает детей (push → apply детям → pull). 151:05 Прибавление к $b_i$ ничего не ломает: если все значения вершины сдвинуть вверх на одно число, точки пересечения не изменятся, поэтому melt остаётся тем же. Менять наклоны таким образом нельзя — точки пересечения могут уйти.
// Kinetic segment tree. Есть массив прямых y_i = k_i * x_i + b_i, у каждой своя точка x_i.
// Запросы: min по отрезку; x_i += dx (dx > 0) на отрезке; b_i += db на отрезке.
const ll KINF = (ll)4e18;
struct KineticSeg {
int n;
vector<ll> k, val, melt, lazyX, lazyB; // k — наклон текущей лучшей прямой, val — её значение,
// melt — на сколько можно сдвинуть x, пока в поддереве ничего не поменяется
KineticSeg(const vector<ll>& K, const vector<ll>& X, const vector<ll>& B) : n(K.size()) {
k.assign(4 * n, 0); val.assign(4 * n, 0); melt.assign(4 * n, KINF); lazyX.assign(4 * n, 0); lazyB.assign(4 * n, 0);
build(1, 0, n, K, X, B);
}
void pull(int v) {
int a = 2 * v, b = 2 * v + 1;
// побеждает меньшее значение; при равенстве — меньший наклон (он останется лучшим при росте x)
bool leftWins = val[a] < val[b] || (val[a] == val[b] && k[a] <= k[b]);
int u = leftWins ? a : b, w = leftWins ? b : a; // u — победитель, w — проигравший
k[v] = k[u]; val[v] = val[u];
melt[v] = min(melt[a], melt[b]);
if (k[w] < k[u]) { // проигравший растёт медленнее — когда-нибудь обгонит
ll d = val[w] - val[u], dk = k[u] - k[w];
melt[v] = min(melt[v], d / dk); // можно сдвинуть не более чем на floor(d/dk)
}
}
void build(int v, int tl, int tr, const vector<ll>& K, const vector<ll>& X, const vector<ll>& B) {
if (tr - tl == 1) { k[v] = K[tl]; val[v] = K[tl] * X[tl] + B[tl]; melt[v] = KINF; return; }
int m = (tl + tr) / 2;
build(2 * v, tl, m, K, X, B); build(2 * v + 1, m, tr, K, X, B); pull(v);
}
void applyB(int v, ll db) { val[v] += db; lazyB[v] += db; }
void applyX(int v, int tl, int tr, ll dx) { // сдвинуть x всех прямых поддерева на dx
if (dx > melt[v]) { // «растаяло»: надо пересчитать детей (у листа melt = INF)
push(v, tl, tr);
int m = (tl + tr) / 2;
applyX(2 * v, tl, m, dx); applyX(2 * v + 1, m, tr, dx);
pull(v);
return;
}
val[v] += k[v] * dx; melt[v] -= dx; lazyX[v] += dx;
}
void push(int v, int tl, int tr) {
int m = (tl + tr) / 2;
if (lazyX[v]) { applyX(2 * v, tl, m, lazyX[v]); applyX(2 * v + 1, m, tr, lazyX[v]); lazyX[v] = 0; }
if (lazyB[v]) { applyB(2 * v, lazyB[v]); applyB(2 * v + 1, lazyB[v]); lazyB[v] = 0; }
}
void addX(int v, int tl, int tr, int l, int r, ll dx) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { applyX(v, tl, tr, dx); return; }
push(v, tl, tr);
int m = (tl + tr) / 2;
addX(2 * v, tl, m, l, r, dx); addX(2 * v + 1, m, tr, l, r, dx); pull(v);
}
void addB(int v, int tl, int tr, int l, int r, ll db) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { applyB(v, db); return; }
push(v, tl, tr);
int m = (tl + tr) / 2;
addB(2 * v, tl, m, l, r, db); addB(2 * v + 1, m, tr, l, r, db); pull(v);
}
ll query(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return KINF;
if (l <= tl && tr <= r) return val[v];
push(v, tl, tr);
int m = (tl + tr) / 2;
return min(query(2 * v, tl, m, l, r), query(2 * v + 1, m, tr, l, r));
}
};Проверка. Код сравнивался с перебором (минимум $k_ix_i+b_i$ после случайных сдвигов $x$ и добавлений к $b$); расхождений не было. Замены прямой в этом варианте нет — это отдельная точечная операция, «обнови путь вверх и пересчитай».
153:05 Проследим жизненный путь одной прямой $\ell$: сначала она побеждает в листе и может «подняться» вверх по дереву, побеждая прямые из соседних поддеревьев (если у неё меньше наклон). Как только она проиграла какой-то прямой навсегда (наклон меньше у соперника и точка пересечения уже позади), она может лишь опускаться вниз. Каждое такое событие KST ловит ровно в момент, когда одна прямая становится лучше другой, и обрабатывает путём спуска. Значит, каждая из $n$ прямых приносит не более $2\log n$ событий — это $O(n\log n)$ событий, а при цене спуска $\log n$ — ещё множитель $\log$.
155:50 При замене прямой «жизненный путь» может сломаться: в вершинах пути, на которые мы повлияли, прямые могут вновь подняться и опуститься — это не более $O(\log n)$ вершин по $2\log n$ событий, то есть $O(\log^2n)$ дополнительных событий на запрос. Прибавление на отрезке затрагивает $\log$ вершин разложения — получается добавка $O(\log^2n)$ событий на запрос. 158:34 Итого: событий $n\log n+Q\log^2n$, на каждое тратим $\log n$, то есть $n\log^2n+Q\log^3n$ — оценка из начала. 159:54 Она сильно завышена: чтобы всё время реализовать худший случай, нужны специальные тесты; поэтому KST на практике работает быстро.
160:35 Лектор отмечает: писать KST действительно просто — самая сложная часть — аккуратное вычисление точки пересечения (округление в нужную сторону, деление отрицательных чисел), всё остальное — классическое ДО с небольшой модификацией.
163:24 Начнём с обычной задачи. Есть массив $a$ и запросы «$a_i\mathrel{+}=x$ на $[l,r)$» и «найти сумму на отрезке в массиве $S$», где $S$ — историческая сумма: если после $k$ запросов были получены массивы $A_1,\dots,A_k$, то $S=A_1+\dots+A_k$ поэлементно.
164:53 Вместо $S$ хранить два массива $D$ и $A$ и считать $S_k=D+A\cdot k$ (где $k$ — число выполненных запросов). Почему так: при запросе $k\to k+1$ массив $S$ получает $A_{k+1}$. Пусть $A_{k+1}=A_k+\delta$. Нужно, чтобы $D_{k+1}+(k+1)A_{k+1}=D_k+kA_k+A_{k+1}$. Отсюда $$D_{k+1}=D_k+kA_k+A_{k+1}-(k+1)A_{k+1}=D_k-k\delta .$$
168:19 Итак, при «$A\mathrel{+}=\delta$ на отрезке» нужно сделать $D\mathrel{-}=k\delta$ на том же отрезке. Оба массива — обычные «прибавление на отрезке, сумма на отрезке», а ответ $\sum D+k\sum A$.
// Историческая сумма: S_k[i] = A_1[i] + ... + A_k[i] — сумма версий массива после каждого из k запросов.
// Храним D и A так, чтобы S_k = D + A * k. При «A[l..r) += x» в момент k делаем A += x и D -= k * x.
struct RangeAddRangeSum { // дерево Фенвика: прибавление на отрезке, сумма на отрезке
int n; vector<ll> b1, b2;
RangeAddRangeSum(int n) : n(n), b1(n + 2), b2(n + 2) {}
void upd(vector<ll>& b, int i, ll v) { for (i++; i <= n + 1; i += i & -i) b[i] += v; }
ll get(vector<ll>& b, int i) { ll s = 0; for (; i > 0; i -= i & -i) s += b[i]; return s; }
void add(int l, int r, ll x) { // [l, r)
upd(b1, l, x); upd(b1, r, -x); upd(b2, l, x * l); upd(b2, r, -x * r);
}
ll prefix(int p) { return get(b1, p) * p - get(b2, p); } // сумма первых p элементов
ll sum(int l, int r) { return prefix(r) - prefix(l); }
};
struct HistoricalSum {
RangeAddRangeSum D, A;
ll k = 0; // сколько запросов изменения уже выполнено
HistoricalSum(int n) : D(n), A(n) {}
void add(int l, int r, ll x) { // выполнить запрос «a[l..r) += x»; получается новая версия массива
A.add(l, r, x);
D.add(l, r, -k * x); // D -= k * x на этом отрезке (k — номер версии до запроса)
k++; // новая версия добавляется в S
}
ll querySum(int l, int r) { return D.sum(l, r) + k * A.sum(l, r); } // сумма S[l..r)
};Проверка. Код сравнивался с честным вычислением $S$ перебором; расхождений не было.
169:40 Запомним, как выглядит обычное ДО:
update(v, l, r, ql, qr, x):
if r <= ql or qr <= l or BREAK(v, x): return // выходим, ничего не меняем
if ql <= l and r <= qr and TAG(v, x): // можно оставить модификатор в вершине
apply(v, x); return
push(v)
update(left(v), ...); update(right(v), ...)
pull(v)173:59 Всё, что мы будем менять от задачи к задаче, — это условия BREAK (break condition) и TAG (tag condition) и то, как применяется модификатор. 174:42 Для обычного ДО BREAK пусто, TAG тоже пусто (достаточно полного покрытия).
a[i] %= x на отрезке, присвоение в точке, сумма 176:07176:07 Запросы: %= x на отрезке, присвоение в точке и сумма. 177:34 BREAK: максимум в вершине меньше $x$ — тогда ни одно число не изменится. 178:14 TAG: можно сделать так, чтобы спуск шёл всегда до листьев (TAG — «длина отрезка равна 1»): лектор утверждает, что это работает быстро.
180:19 Доказательство через потенциал. Вершины, посещённые запросом, бывают трёх типов:
185:07 Потенциал: $\Phi=\sum_v\varphi(v)$, где $\varphi(v)=\sum_{i\in v}\log_2(a_i+1)$ — сумма логарифмов чисел на отрезке вершины. 185:50 Каждое значение входит ровно в одну вершину уровня и вносит вклад $\le\log C$, поэтому начальный $\Phi\le n\log n\log C$. 186:31 %= потенциал только уменьшает, запрос суммы его не меняет, а присвоение в точке увеличивает $\Phi$ не более чем на $\log n\log C$. Итого «монеток» создаётся не более $n\log n\log C+Q\log n\log C$. 187:52 Каждая дополнительная вершина съедает монетку: в ней есть число $a\ge x$, а при $a\bmod x$ число уменьшается хотя бы вдвое, то есть $\log a$ уменьшается минимум на 1. Значит, всего дополнительных вершин $O((n+Q)\log n\log C)$, и такова же оценка на всё время.
Исправление. В итоговой формуле на записи озвучено «$(Q+n)\log C$» (без $\log n$); строгая оценка для этого потенциала содержит и $\log n$ — каждый элемент учитывается в $\log n$ вершинах.
Отдельно: условие «спускаемся, только если $L+1<R$» лектор сам поправил в записи — спуск продолжается, пока отрезок длиннее одного элемента, а в листе ставится тег.
chmin, максимум, сумма 189:55190:39 Запросы: chmin на отрезке, максимум на отрезке и сумма на отрезке. 192:06 BREAK: максимум вершины $\le x$ — ничего не поменяется. 192:46 TAG: $x$ строго больше второго максимума вершины (второй максимум — второе по величине различное значение; если все 100 чисел равны, второго нет). Тогда chmin меняет только все максимумы сразу, и модификатор можно оставить в вершине. 193:27 Для этого в вершине храним максимум, второй максимум, количество максимумов и сумму. Применение: $\mathrm{sum}\mathrel{-}=(\mathrm{mx}-x)\cdot\mathrm{cnt}$, затем $\mathrm{mx}=x$.
194:48 Потенциал. $\Phi=\sum_v\varphi(v)$, где $\varphi(v)$ — число различных значений на отрезке вершины ($\le$ длины). 195:29 На одном уровне суммарно $\le n$, всего $\Phi\le n\log n$. Запросы максимума и суммы массив не меняют. 196:10 При chmin потенциал вершины, целиком лежащей в запросе, только уменьшается (значения склеиваются — «пресс сверху»); в вершине, не пересекающейся с запросом, не меняется; а в вершинах, пересекающих отрезок запроса лишь частично, $\varphi$ растёт не более чем на 1, их $O(\log n)$. 198:54 Каждая дополнительная вершина — это та, где $x\le$ второго максимума, то есть максимум и второй максимум склеиваются: $\varphi$ падает хотя бы на 1. Итого $O((n+Q)\log n)$ — ровно как обычное ДО плюс $n\log n$ на начальный потенциал.
201:00 Добавим chmax, прибавление на отрезке и присвоение (присвоение можно выразить через chmin и chmax одновременно). В вершине храним максимум, второй максимум, количество максимумов, то же для минимума, и сумму. 203:02 chmax симметричен: BREAK — минимум $\ge x$, TAG — $x<$ второго минимума. 203:43 Удобнее хранить сумму отдельно (без учёта экстремумов), но в коде ниже — просто общая сумма и количества.
204:24 Старый потенциал ломается из-за +=. Пример: $[1,2,\dots,n/2,1,2,\dots,n/2]$: в корне $\varphi=n/2$, но после += n/2 на левой половине все $n$ значений становятся различными — потенциал вырос на $\Theta(n)$ за запрос, и оценка $Qn$ никуда не годится. 205:51 Новый потенциал: $\Phi=\Phi_1+\Phi_2$, где $\Phi_1$ — число вершин, у которых максимум левого ребёнка не равен максимуму правого, а $\Phi_2$ — то же для минимума (206:33).
+= — прибавление ко всем сразу не меняет сравнения внутри целиком накрытых вершин; для chmin потенциал $\Phi_1$ увеличивается только в вершинах, у которых максимумы были равны, а теперь различны — значит, у вершины есть и изменённая, и неизменённая часть, и она пересекает отрезок запроса — тоже не более $O(\log n)$ вершин (209:21). Суммарное увеличение $O(Q\log n)$.chmin станут равными — потенциал уменьшился на 1. Все дополнительные вершины лежат на путях вверх от таких «исправившихся» вершин, а длина пути не больше $\log n$, поэтому число дополнительных вершин $\le\log n\cdot(\text{число исправившихся вершин})$ (214:44).216:07 Как писать: все запросы, кроме двух (chmin и chmax), ровно как в обычном ДО; нужно лишь аккуратно продумать, как модификатор меняет значения в вершине.
// Segment Tree Beats: chmin, chmax, add на отрезке; sum, min, max на отрезке.
const ll BINF = (ll)4e18;
struct Beats {
struct Node { ll sum, mx, smx, mn, smn, add; int cmx, cmn, len; };
int n; vector<Node> t;
Beats(const vector<ll>& a) : n(a.size()), t(4 * a.size()) { build(1, 0, n, a); }
void pull(int v) {
Node &x = t[v], &l = t[2 * v], &r = t[2 * v + 1];
x.sum = l.sum + r.sum;
// максимум, второй максимум и количество максимумов
if (l.mx > r.mx) { x.mx = l.mx; x.cmx = l.cmx; x.smx = max(l.smx, r.mx); }
else if (l.mx < r.mx) { x.mx = r.mx; x.cmx = r.cmx; x.smx = max(l.mx, r.smx); }
else { x.mx = l.mx; x.cmx = l.cmx + r.cmx; x.smx = max(l.smx, r.smx); }
// то же для минимума
if (l.mn < r.mn) { x.mn = l.mn; x.cmn = l.cmn; x.smn = min(l.smn, r.mn); }
else if (l.mn > r.mn) { x.mn = r.mn; x.cmn = r.cmn; x.smn = min(l.mn, r.smn); }
else { x.mn = l.mn; x.cmn = l.cmn + r.cmn; x.smn = min(l.smn, r.smn); }
}
void build(int v, int tl, int tr, const vector<ll>& a) {
t[v].add = 0; t[v].len = tr - tl;
if (tr - tl == 1) { t[v].sum = t[v].mx = t[v].mn = a[tl]; t[v].smx = -BINF; t[v].smn = BINF; t[v].cmx = t[v].cmn = 1; return; }
int m = (tl + tr) / 2; build(2 * v, tl, m, a); build(2 * v + 1, m, tr, a); pull(v);
}
void applyAdd(int v, ll x) {
Node& a = t[v];
a.sum += x * a.len; a.mx += x; a.mn += x; a.add += x;
if (a.smx != -BINF) a.smx += x;
if (a.smn != BINF) a.smn += x;
}
void applyMin(int v, ll x) { // «все максимумы стали x»; требуется x > второго максимума
Node& a = t[v];
if (x >= a.mx) return;
a.sum -= (a.mx - x) * a.cmx;
if (a.mn == a.mx) a.mn = x; // все числа одинаковы
else if (a.smn == a.mx) a.smn = x; // два различных значения
a.mx = x;
}
void applyMax(int v, ll x) {
Node& a = t[v];
if (x <= a.mn) return;
a.sum += (x - a.mn) * a.cmn;
if (a.mx == a.mn) a.mx = x;
else if (a.smx == a.mn) a.smx = x;
a.mn = x;
}
void push(int v) {
if (t[v].add) { applyAdd(2 * v, t[v].add); applyAdd(2 * v + 1, t[v].add); t[v].add = 0; }
for (int c : {2 * v, 2 * v + 1}) { applyMin(c, t[v].mx); applyMax(c, t[v].mn); }
}
void chmin(int v, int tl, int tr, int l, int r, ll x) {
if (r <= tl || tr <= l || t[v].mx <= x) return; // break condition: ничего не изменится
if (l <= tl && tr <= r && t[v].smx < x) { applyMin(v, x); return; } // tag condition: меняются только максимумы
push(v);
int m = (tl + tr) / 2;
chmin(2 * v, tl, m, l, r, x); chmin(2 * v + 1, m, tr, l, r, x); pull(v);
}
void chmax(int v, int tl, int tr, int l, int r, ll x) {
if (r <= tl || tr <= l || t[v].mn >= x) return;
if (l <= tl && tr <= r && t[v].smn > x) { applyMax(v, x); return; }
push(v);
int m = (tl + tr) / 2;
chmax(2 * v, tl, m, l, r, x); chmax(2 * v + 1, m, tr, l, r, x); pull(v);
}
void add(int v, int tl, int tr, int l, int r, ll x) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { applyAdd(v, x); return; }
push(v);
int m = (tl + tr) / 2;
add(2 * v, tl, m, l, r, x); add(2 * v + 1, m, tr, l, r, x); pull(v);
}
ll sum(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return 0;
if (l <= tl && tr <= r) return t[v].sum;
push(v);
int m = (tl + tr) / 2;
return sum(2 * v, tl, m, l, r) + sum(2 * v + 1, m, tr, l, r);
}
ll getMax(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return -BINF;
if (l <= tl && tr <= r) return t[v].mx;
push(v);
int m = (tl + tr) / 2;
return max(getMax(2 * v, tl, m, l, r), getMax(2 * v + 1, m, tr, l, r));
}
};Проверка. Код сравнивался с перебором на 1500 случайных тестов из 40 операций (chmin, chmax, +=, сумма, максимум); расхождений не было. Запрос минимума реализуется так же, как максимум.
217:30 Оставим запросы: chmin, += и $\gcd$ на отрезке. Без chmin — классический трюк: $\gcd(a_1,\dots,a_k)=\gcd(a_1,a_2-a_1,\dots)$; 218:52 разности образуют дерево (одно число оставляем, остальные заменяем на разности с другими числами). При += x на отрезке все разности внутри не меняются, меняется только «представитель». Храним $\gcd$ по разностям и представителя; при проталкивании модификатора меняется только он. 220:14 Чтобы вернуть chmin: в качестве представителя берём максимум отрезка (он не меняется разностями) и отдельно храним второй максимум. Тогда при применении chmin (TAG — $x>$ второго максимума) меняется только максимум, а в разностях участвует второй максимум, как «реальное» число. 221:36 При слиянии двух поддеревьев объединяем деревья разностей. Идея без кода.
222:57 Если вместо присвоения в точке разрешить присвоение на отрезке (вместе с %= и суммой), старое доказательство потенциала ломается (сумма логарифмов на отрезке меняется сразу в $\Theta(n)$ местах). Решение почти не меняется: BREAK — максимум вершины меньше $x$; TAG — максимум равен минимуму (все числа равны): тогда присваиваем всему отрезку число $\max\bmod x$. 224:22 Потенциал нужно выбрать иначе (лектор подробности опускает).
224:22 Запросы: +=, сумма, минимум, максимум и «$a_i=\lfloor\sqrt{a_i}\rfloor$ на отрезке» (числа неотрицательны). 225:03 BREAK не нужен (точнее, можно ничего не ставить). TAG: $\max-\min\le1$. 226:27 В этом случае после взятия корня возможны два исхода: либо все числа станут одинаковыми — тогда присваиваем им это число, либо останутся различными (отличаются на 1) — тогда все числа уменьшаются на одно и то же, и делаем += на отрезке. То же верно для $\lfloor a_i/x\rfloor$ (деление на параметр запроса).
// Запросы: add на отрезке, a_i = floor(sqrt(a_i)) на отрезке, sum на отрезке. Числа неотрицательны.
ll isqrtFloor(ll x) { ll r = sqrtl((long double)x); while (r * r > x) r--; while ((r + 1) * (r + 1) <= x) r++; return r; }
struct SqrtSeg {
struct Node { ll sum, mx, mn; int mode; ll val; }; // mode: 0 — нет тега, 1 — «+= val», 2 — «= val»
int n; vector<Node> t;
SqrtSeg(const vector<ll>& a) : n(a.size()), t(4 * a.size()) { build(1, 0, n, a); }
void pull(int v) { t[v].sum = t[2*v].sum + t[2*v+1].sum; t[v].mx = max(t[2*v].mx, t[2*v+1].mx); t[v].mn = min(t[2*v].mn, t[2*v+1].mn); }
void build(int v, int tl, int tr, const vector<ll>& a) {
t[v].mode = 0;
if (tr - tl == 1) { t[v].sum = t[v].mx = t[v].mn = a[tl]; return; }
int m = (tl + tr) / 2; build(2*v, tl, m, a); build(2*v+1, m, tr, a); pull(v);
}
void applyAdd(int v, int len, ll x) {
t[v].sum += x * len; t[v].mx += x; t[v].mn += x;
if (t[v].mode == 0) { t[v].mode = 1; t[v].val = x; } else t[v].val += x; // «+=» после «=» или «+=» — просто складываем
}
void applyAssign(int v, int len, ll x) { t[v].sum = x * len; t[v].mx = t[v].mn = x; t[v].mode = 2; t[v].val = x; }
void push(int v, int tl, int tr) {
int m = (tl + tr) / 2;
if (t[v].mode == 1) { applyAdd(2*v, m - tl, t[v].val); applyAdd(2*v+1, tr - m, t[v].val); }
else if (t[v].mode == 2) { applyAssign(2*v, m - tl, t[v].val); applyAssign(2*v+1, tr - m, t[v].val); }
t[v].mode = 0;
}
void add(int v, int tl, int tr, int l, int r, ll x) {
if (r <= tl || tr <= l) return;
if (l <= tl && tr <= r) { applyAdd(v, tr - tl, x); return; }
push(v, tl, tr); int m = (tl + tr) / 2;
add(2*v, tl, m, l, r, x); add(2*v+1, m, tr, l, r, x); pull(v);
}
void sqrtOp(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return;
// tag condition: max - min <= 1, тогда после корня либо все числа равны, либо все уменьшатся на одно и то же
if (l <= tl && tr <= r && t[v].mx - t[v].mn <= 1) {
ll a = isqrtFloor(t[v].mx), b = isqrtFloor(t[v].mn);
if (a == b) applyAssign(v, tr - tl, a);
else applyAdd(v, tr - tl, a - t[v].mx); // a - mx == b - mn
return;
}
push(v, tl, tr); int m = (tl + tr) / 2;
sqrtOp(2*v, tl, m, l, r); sqrtOp(2*v+1, m, tr, l, r); pull(v);
}
ll sum(int v, int tl, int tr, int l, int r) {
if (r <= tl || tr <= l) return 0;
if (l <= tl && tr <= r) return t[v].sum;
push(v, tl, tr); int m = (tl + tr) / 2;
return sum(2*v, tl, m, l, r) + sum(2*v+1, m, tr, l, r);
}
};Проверка. Код сравнивался с перебором на 1000 случайных тестов (+=, корень, сумма); расхождений не было.
227:08 В конце лектор рекомендует прочитать «замечательный блог» с несколькими дополнительными задачами на эту технику (ссылку обещал прислать отдельно).