0:09 Sparse table отвечает на запросы «минимум на отрезке» за $O(1)$ после предподсчёта за $O(n\log n)$ времени и памяти. Пусть $dp[i][j]$ — минимум на полуинтервале $[j,\,j+2^i)$. Тогда $$dp[0][j]=a_j,\qquad dp[i][j]=\min\bigl(dp[i-1][j],\ dp[i-1][j+2^{i-1}]\bigr).$$ Запрос $[L,R)$: берём $k=\lfloor\log_2(R-L)\rfloor$ и отвечаем $\min(dp[k][L],\ dp[k][R-2^k])$ — два блока длины $2^k$ покрывают отрезок целиком и перекрываются. Для минимума перекрытие не мешает.
Логарифм можно получить тремя способами: заранее посчитанным массивом lg[i] = lg[i/2] + 1, функцией __lg(x) или через 31 - __builtin_clz(x). Массив надёжнее всего, остальные работают за одну инструкцию.
// Sparse table для минимума: dp[i][j] = min на полуинтервале [j, j + 2^i)
struct SparseTable {
vector<vector<int>> dp;
vector<int> lg;
SparseTable(const vector<int>& a) {
int n = a.size();
lg.assign(n + 1, 0);
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1; // lg[i] = floor(log2 i)
dp.assign(lg[n] + 1, vector<int>(n));
dp[0] = a; // база: отрезки длины 1
for (int i = 1; i <= lg[n]; i++)
for (int j = 0; j + (1 << i) <= n; j++)
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]);
}
int get(int l, int r) const { // минимум на [l, r), l < r
int k = lg[r - l];
return min(dp[k][l], dp[k][r - (1 << k)]); // два перекрывающихся отрезка длины 2^k
}
};6:39 Задача: стек, в котором есть push, pop и запрос минимума на любом куске стека (на отрезке по номерам). Идея: хранить sparse table «назад»: $dp[i][j]$ — минимум на $2^i$ элементах, заканчивающихся в позиции $j$. Тогда добавление элемента в позицию $j$ трогает только его собственный столбец: $dp[i][j]=\min(dp[i-1][j],\ dp[i-1][j-2^{i-1}])$ за $O(\log n)$, а удаление — просто уменьшение размера стека, ведь старые значения «слева» не менялись.
push — $O(\log n)$;pop — $O(1)$;Лектор советует упрощать реализацию: стек растёт не вправо, а от позиции $n$ влево, чтобы не заводить отдельный указатель — «упрощайте реализацию, если можно». В коде ниже для наглядности стек растёт вправо.
// Стек с минимумом на отрезке [l, r) по индексам стека: push — O(log n), pop — O(1), запрос — O(1).
// Хранится «зеркально»: sparse table считается НАЗАД от позиции — dp[i][j] = min на [j - 2^i + 1, j] (включительно),
// поэтому добавление элемента меняет значения только в его собственной позиции.
struct StackMin {
int sz = 0;
vector<vector<int>> dp; // dp[i][j]: минимум на 2^i элементах, заканчивающихся в позиции j
vector<int> lg, a;
StackMin(int maxn) : dp(__lg(maxn) + 1, vector<int>(maxn)), lg(maxn + 2, 0), a(maxn) {
for (int i = 2; i <= maxn + 1; i++) lg[i] = lg[i / 2] + 1;
}
void push(int x) {
int j = sz++;
a[j] = x;
dp[0][j] = x;
for (int i = 1; i < (int)dp.size() && j - (1 << i) + 1 >= 0; i++)
dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - (1 << (i - 1))]);
}
void pop() { sz--; }
int get(int l, int r) const { // индексы в стеке, [l, r), l < r <= sz
int k = lg[r - l];
return min(dp[k][r - 1], dp[k][l + (1 << k) - 1]);
}
};13:00 Вместо $\min$ можно взять любую функцию $f$, если она:
Этим условиям удовлетворяют $\min$, $\max$, $\gcd$, побитовые AND/OR. Сумма и произведение не подходят (нет идемпотентности) — для них нужна другая структура, см. ниже.
Важное дополнение. Коммутативность на самом деле можно ослабить: если блоки брать в порядке «левый, правый», хватит ассоциативности и идемпотентности. Но на практике все нужные операции коммутативны.
14:43 Вопрос из чата: в формуле $dp[i][j]$ надо ли ограничивать правую границу? Лектор поясняет: в записи $j+2^i$ на самом деле подразумевается $\min(n,\,j+2^i)$, но «брейкать» ничего не нужно. База динамики хранит реальный массив, а элементы правее $n$ считаются неопределёнными; значения каждого следующего слоя пересчитываются только из значений текущих слоёв, поэтому выход в отрицательную или за-правую зону не происходит.
16:21 Нужно отвечать на запрос $\prod_{i=l}^{r}a_i \bmod M$. Если $M$ простое и все $a_i\not\equiv0$, считаем префиксные произведения $P_i$ и обратные к ним: ответ $P_r\cdot P_{l-1}^{-1}$. Проблема — элементы, кратные $M$. Выход: записываем $a_i=M^{k}\cdot r$, где $r$ не делится на $M$. Храним префиксные произведения именно $r$ и префиксные суммы $k$. Если сумма $k$ на отрезке положительна — ответ $0$ (в произведении есть множитель $M$), иначе ответ — отношение произведений $r$.
// Произведение на отрезке по простому модулю M за O(1) при любых a[i] (в том числе кратных M).
// a[i] = M^k * r, где r не делится на M (для a[i] = 0 считаем k огромным). Храним префиксные произведения r и префиксные суммы k.
typedef long long ll;
ll power(ll b, ll e, ll mod) { ll r = 1; b %= mod; while (e) { if (e & 1) r = r * b % mod; b = b * b % mod; e >>= 1; } return r; }
struct ProductPrime {
ll M;
vector<ll> prodR, invR; // префиксные произведения r и их обратные по модулю
vector<ll> cntK; // префиксные суммы показателей k
ProductPrime(const vector<ll>& a, ll M) : M(M), prodR(a.size() + 1, 1), invR(a.size() + 1, 1), cntK(a.size() + 1, 0) {
for (size_t i = 0; i < a.size(); i++) {
ll r = a[i], k = 0;
if (r == 0) { r = 1; k = 1000000000; } // нуль делится на M сколько угодно раз
while (r % M == 0) { r /= M; k++; } // выделяем максимальную степень M
prodR[i + 1] = prodR[i] * (r % M) % M;
cntK[i + 1] = cntK[i] + k;
}
for (size_t i = 0; i <= a.size(); i++) invR[i] = power(prodR[i], M - 2, M); // r взаимно просто с M — обратный есть
}
ll get(int l, int r) const { // произведение a[l..r) по модулю M
if (cntK[r] - cntK[l] > 0) return 0; // в произведении есть множитель M
return prodR[r] * invR[l] % M;
}
};25:36 Если $M$ составное, обратных элементов нет, и деление невозможно. Тогда нужна структура, которая отвечает без деления. Берём полное дерево отрезков (длину массива дополняем до степени двойки) и в каждой вершине храним:
Запрос $[l,r]$ ($l\ne r$): вершина дерева, в которой $l$ и $r$ расходятся, задаётся старшим битом $l\oplus r$ — это номер уровня; номер блока на уровне — $l\gg\text{level}$. Ответ — произведение суффикса от $l$ до середины и префикса от середины до $r$, всего одно умножение, то есть $O(1)$. Память $O(n\log n)$ — по числу на каждый уровень и каждую позицию.
Важное дополнение. Эта структура называется disjoint sparse table. Она работает для любой ассоциативной операции (даже некоммутативной, если соблюдать порядок), поскольку два используемых куска не перекрываются. Случай $l=r$ обрабатывается отдельно: ответ — сам элемент.
// Disjoint sparse table: любая ассоциативная операция, запрос за O(1), память O(n log n). n округляем до степени двойки.
template <class T, class Op>
struct DisjointSparse {
int n, LOG;
Op op;
vector<vector<T>> t; // t[h][i]: на уровне h блоки по 2^(h+1); слева от середины — суффиксы, справа — префиксы
vector<T> a;
DisjointSparse(vector<T> v, Op op) : op(op) {
n = 1; LOG = 0;
while (n < (int)v.size()) n *= 2, LOG++;
T pad = v.empty() ? T() : v[0];
v.resize(n, pad);
a = v;
t.assign(max(LOG, 1), vector<T>(n));
for (int h = 0; h < LOG; h++) {
int half = 1 << h;
for (int start = 0; start < n; start += 2 * half) {
int mid = start + half;
t[h][mid - 1] = v[mid - 1];
for (int i = mid - 2; i >= start; i--) t[h][i] = op(v[i], t[h][i + 1]); // суффиксы левой половины
t[h][mid] = v[mid];
for (int i = mid + 1; i < start + 2 * half; i++) t[h][i] = op(t[h][i - 1], v[i]); // префиксы правой
}
}
}
T get(int l, int r) const { // на отрезке [l, r] включительно
if (l == r) return a[l];
int h = 31 - __builtin_clz(l ^ r); // старший бит l xor r — уровень, на котором l и r разошлись
return op(t[h][l], t[h][r]);
}
};40:40 Мажоранта отрезка — элемент, встречающийся строго больше половины раз. Нужно ответить, есть ли она на $[l,r]$, и какова. Разберём способы.
map позиций и бинпоиску). $O(30\log n)$ на запрос.Во всех способах найденного кандидата надо проверить: для каждого значения хранится отсортированный список позиций, и число вхождений на $[l,r]$ считается двумя бинарными поисками. Кандидат — мажоранта, если вхождений больше $(r-l+1)/2$.
Важное дополнение. Пара $(x,\text{cnt})$ гарантирует лишь одно: если на отрезке есть мажоранта, то она равна $x$. Если мажоранты нет, $x$ может быть любым элементом — поэтому найденного кандидата всегда проверяют подсчётом вхождений.
// Мажорантa на отрезке: число, встречающееся строго больше половины раз.
// Пара (x, cnt): x — кандидат, cnt — сколько «непарных» копий x осталось. Две пары сливаются за O(1).
typedef pair<int,int> Cand;
Cand mergeCand(Cand a, Cand b) {
if (a.first == b.first) return {a.first, a.second + b.second};
if (a.second >= b.second) return {a.first, a.second - b.second}; // непарные элементы гасят друг друга
return {b.first, b.second - a.second};
}
struct MajorityQuery {
map<int, vector<int>> pos; // позиции каждого значения (отсортированы)
DisjointSparse<Cand, Cand(*)(Cand, Cand)> ds;
MajorityQuery(const vector<int>& a)
: ds([&] { vector<Cand> v; for (int x : a) v.push_back({x, 1}); return v; }(), mergeCand) {
for (size_t i = 0; i < a.size(); i++) pos[a[i]].push_back(i);
}
// ответ на отрезке [l, r] включительно: значение или -1, если мажоранты нет
int get(int l, int r) {
Cand c = ds.get(l, r);
auto& p = pos[c.first];
int cnt = upper_bound(p.begin(), p.end(), r) - lower_bound(p.begin(), p.end(), l); // проверка кандидата бинпоиском
return 2 * cnt > r - l + 1 ? c.first : -1;
}
};59:21 Задача: минимум на подпрямоугольнике таблицы $n\times m$. Для квадратов $2^k\times2^k$ можно взять один квадрат — но запрос произвольного прямоугольника не сводится к степеням двойки одновременно по обеим сторонам. Решение: степени двойки по осям независимы: $dp[a][b][i][j]$ — минимум на блоке $2^a\times2^b$ с левым верхним углом $(i,j)$. Запрос покрывается четырьмя перекрывающимися блоками, ответ — минимум четырёх значений, $O(1)$; память $O(nm\log n\log m)$.
// 2D sparse table для минимума: независимые степени двойки по строкам и столбцам. Память и предподсчёт O(nm log n log m), запрос O(1)
struct Sparse2D {
int n, m;
vector<vector<vector<vector<int>>>> t; // t[a][b][i][j]: min на [i, i+2^a) x [j, j+2^b)
vector<int> lg;
Sparse2D(const vector<vector<int>>& g) : n(g.size()), m(g[0].size()) {
int mx = max(n, m);
lg.assign(mx + 1, 0);
for (int i = 2; i <= mx; i++) lg[i] = lg[i / 2] + 1;
t.assign(lg[n] + 1, vector<vector<vector<int>>>(lg[m] + 1));
for (int a = 0; a <= lg[n]; a++)
for (int b = 0; b <= lg[m]; b++) {
t[a][b].assign(n, vector<int>(m, INT_MAX));
for (int i = 0; i + (1 << a) <= n; i++)
for (int j = 0; j + (1 << b) <= m; j++) {
if (a == 0 && b == 0) t[a][b][i][j] = g[i][j];
else if (a == 0) t[a][b][i][j] = min(t[a][b - 1][i][j], t[a][b - 1][i][j + (1 << (b - 1))]);
else t[a][b][i][j] = min(t[a - 1][b][i][j], t[a - 1][b][i + (1 << (a - 1))][j]);
}
}
}
int get(int r1, int c1, int r2, int c2) const { // прямоугольник [r1, r2) x [c1, c2)
int a = lg[r2 - r1], b = lg[c2 - c1];
return min(min(t[a][b][r1][c1], t[a][b][r2 - (1 << a)][c1]),
min(t[a][b][r1][c2 - (1 << b)], t[a][b][r2 - (1 << a)][c2 - (1 << b)])); // 4 перекрывающихся прямоугольника
}
};Дальше в записи (примерно 1:05–1:08) идут вопросы из чата, не относящиеся к теме: sparse table встречается в задачах не слишком часто, но идея полезна — её применяют, например, для запросов LCP в суффиксном массиве (будет позже); дерево отрезков универсальнее, а sparse table на запросе быстрее.
68:06 Декартово дерево (treap) — бинарное дерево, одновременно: дерево поиска по ключу $x$ и куча по приоритету $y$ (приоритет родителя больше/меньше приоритетов детей — условимся: меньше). Если приоритеты — случайные различные числа, то форма дерева — такая же, как у дерева, построенного вставкой ключей в случайном порядке, и ожидаемая глубина — $O(\log n)$.
Развёрнутое объяснение (оценка глубины). Вершина $j$ является предком вершины $i$ тогда и только тогда, когда у $j$ наименьший приоритет среди всех вершин между ними (включая оба конца). Вероятность этого равна $\frac1{|i-j|+1}$, значит ожидаемая глубина вершины $i$ — сумма $\sum_{j\ne i}\frac1{|i-j|+1}\le 2H_n=O(\log n)$ — гармонический ряд.
Все операции выражаются через две.
Через них получаем:
sz и спускаемся, сравнивая $k$ с размером левого поддерева (пересчёт sz — функция update, вызывается после любого изменения детей);// Декартово дерево по ключу: ключи — бинарное дерево поиска, приоритеты y — куча (у корня приоритет максимален)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 200005;
int L[MAXN], R[MAXN], sz[MAXN], cntNodes = 0;
unsigned Y[MAXN];
int X[MAXN];
int newNode(int x) { int v = ++cntNodes; X[v] = x; Y[v] = rng(); L[v] = R[v] = 0; sz[v] = 1; return v; }
void upd(int v) { if (v) sz[v] = sz[L[v]] + sz[R[v]] + 1; } // sz[0] = 0 — «сторожевой» нулевой узел
// merge: все ключи в a меньше всех ключей в b
int merge(int a, int b) {
if (!a) return b;
if (!b) return a;
if (Y[a] > Y[b]) { R[a] = merge(R[a], b); upd(a); return a; } // корнем становится вершина с большим приоритетом
L[b] = merge(a, L[b]); upd(b); return b;
}
// split: (ключи <= k) и (ключи > k)
pair<int,int> split(int t, int k) {
if (!t) return {0, 0};
if (X[t] <= k) { auto q = split(R[t], k); R[t] = q.first; upd(t); return {t, q.second}; }
auto q = split(L[t], k); L[t] = q.second; upd(t); return {q.first, t};
}
void insertKey(int& root, int x) { // ключи считаем различными
auto q = split(root, x);
root = merge(merge(q.first, newNode(x)), q.second);
}
void eraseKey(int& root, int x) {
auto q = split(root, x); // q.first: <= x
auto p = split(q.first, x - 1); // p.first: <= x-1, p.second: ровно вершина с ключом x
root = merge(p.first, q.second); // вершину p.second выбрасываем
}
int kth(int t, int k) { // k-й по порядку (с единицы): спуск по размерам
while (t) {
if (k <= sz[L[t]]) t = L[t];
else if (k == sz[L[t]] + 1) return X[t];
else k -= sz[L[t]] + 1, t = R[t];
}
return -1;
}Ключ можно не хранить: ключ вершины — её номер в массиве, который восстанавливается по размерам поддеревьев. Индекс вершины $v$ = $sz[\text{left}(v)]$ плюс по пути к корню: каждый раз, когда поднимаемся из правого сына, прибавляем $sz[\text{left}(p)]+1$ для родителя $p$.
Теперь split/merge работают не по ключу, а по размеру: split(T, k) отрезает первые $k$ элементов. Отсюда:
rev; при проходе вниз (push) меняем местами детей и переносим флаг. Режем отрезок split-ами, помечаем и склеиваем;// Неявное декартово дерево: хранит массив. Ключ — позиция (в дереве не хранится), приоритеты случайны.
// Операции: вставка/удаление по индексу, сумма на отрезке, += на отрезке, разворот отрезка.
const int MAXN = 200005;
int L[MAXN], R[MAXN], sz[MAXN], cnt = 0;
unsigned Y[MAXN];
long long val[MAXN], sum[MAXN], addLazy[MAXN];
bool rev[MAXN];
int newNode(long long x) { int v = ++cnt; val[v] = sum[v] = x; Y[v] = rng(); sz[v] = 1; L[v] = R[v] = 0; return v; }
void apply_add(int v, long long d) { if (v) { val[v] += d; sum[v] += d * sz[v]; addLazy[v] += d; } }
void apply_rev(int v) { if (v) { swap(L[v], R[v]); rev[v] ^= 1; } }
void push(int v) { // протолкнуть отложенные операции детям
if (rev[v]) { apply_rev(L[v]); apply_rev(R[v]); rev[v] = false; }
if (addLazy[v]) { apply_add(L[v], addLazy[v]); apply_add(R[v], addLazy[v]); addLazy[v] = 0; }
}
void upd(int v) { if (v) { sz[v] = sz[L[v]] + sz[R[v]] + 1; sum[v] = sum[L[v]] + sum[R[v]] + val[v]; } }
int merge(int a, int b) {
if (!a || !b) return a ? a : b;
if (Y[a] > Y[b]) { push(a); R[a] = merge(R[a], b); upd(a); return a; }
push(b); L[b] = merge(a, L[b]); upd(b); return b;
}
pair<int,int> split(int t, int k) { // (первые k элементов, остальные)
if (!t) return {0, 0};
push(t);
if (sz[L[t]] < k) { auto q = split(R[t], k - sz[L[t]] - 1); R[t] = q.first; upd(t); return {t, q.second}; }
auto q = split(L[t], k); L[t] = q.second; upd(t); return {q.first, t};
}
void insertAt(int& root, int pos, long long x) { // стать элементом с индексом pos (с нуля)
auto q = split(root, pos);
root = merge(merge(q.first, newNode(x)), q.second);
}
void eraseAt(int& root, int pos) {
auto a = split(root, pos), b = split(a.second, 1);
root = merge(a.first, b.second);
}
long long rangeSum(int& root, int l, int r) { // [l, r)
auto a = split(root, l), b = split(a.second, r - l);
long long res = sum[b.first];
root = merge(a.first, merge(b.first, b.second));
return res;
}
void rangeAdd(int& root, int l, int r, long long d) {
auto a = split(root, l), b = split(a.second, r - l);
apply_add(b.first, d);
root = merge(a.first, merge(b.first, b.second));
}
void rangeReverse(int& root, int l, int r) {
auto a = split(root, l), b = split(a.second, r - l);
apply_rev(b.first);
root = merge(a.first, merge(b.first, b.second));
}Важное дополнение (проверено замером). В merge нельзя выбирать корень «подбрасыванием монетки» (rand()%2) вместо сравнения приоритетов: форма дерева перестаёт быть декартовой и глубина вырождается. Я проверил: при $n=16000$ последовательных вставок глубина оказалась порядка 7973, а при честных приоритетах — около 34. Для неявного дерева вместо приоритетов допустимо выбирать корень с вероятностью, пропорциональной размеру: $\Pr[\text{левый}]=\frac{sz_L}{sz_L+sz_R}$ — это эквивалентно случайным приоритетам.
117:49 Задача: на отрезке $[l,r]$ посчитать количество чисел в диапазоне $[x,y]$. Строим дерево отрезков, в каждой вершине хранится отсортированный массив значений отрезка. Строится слиянием детей, как в сортировке слиянием, за $O(n\log n)$ времени и памяти. Запрос: $O(\log n)$ вершин, в каждой два бинарных поиска — $O(\log^2 n)$.
Смысл метода — геометрический: превратим элементы в точки $(i,a_i)$ на плоскости, запрос — число точек в прямоугольнике $[l,r]\times[x,y]$. Дерево по $i$, внутри — структура по $a_i$.
Если значения меняются, отсортированные массивы заменяют на деревья Фенвика внутри вершин (по сжатым координатам $a_i$) — получаем двумерное дерево Фенвика; сжатие координат можно заменить неявным Фенвиком (словарь unordered_map по нужным индексам).
// Merge sort tree: в каждой вершине дерева отрезков хранится отсортированный список значений её отрезка.
// Запрос: сколько чисел из [x, y] на отрезке индексов [l, r) — O(log^2 n).
struct MergeSortTree {
int n;
vector<vector<int>> t;
MergeSortTree(const vector<int>& a) : n(a.size()), t(4 * a.size()) { build(1, 0, n, a); }
void build(int v, int l, int r, const vector<int>& a) {
if (r - l == 1) { t[v] = {a[l]}; return; }
int mid = (l + r) / 2;
build(2 * v, l, mid, a); build(2 * v + 1, mid, r, a);
t[v].resize(r - l);
merge(t[2 * v].begin(), t[2 * v].end(), t[2 * v + 1].begin(), t[2 * v + 1].end(), t[v].begin()); // как в сортировке слиянием
}
int count(int v, int l, int r, int ql, int qr, int x, int y) const { // значения в [x, y]
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) // вершина целиком внутри запроса: два бинпоиска
return upper_bound(t[v].begin(), t[v].end(), y) - lower_bound(t[v].begin(), t[v].end(), x);
int mid = (l + r) / 2;
return count(2 * v, l, mid, ql, qr, x, y) + count(2 * v + 1, mid, r, ql, qr, x, y);
}
int count(int l, int r, int x, int y) const { return count(1, 0, n, l, r, x, y); }
};// Двумерное дерево Фенвика: сумма на префиксном прямоугольнике и точечное изменение — два вложенных цикла вместо одного
struct Fenwick2D {
int n, m;
vector<vector<long long>> t;
Fenwick2D(int n, int m) : n(n), m(m), t(n + 1, vector<long long>(m + 1, 0)) {}
void add(int x, int y, long long d) { // x, y — с нуля
for (int i = x + 1; i <= n; i += i & -i)
for (int j = y + 1; j <= m; j += j & -j) t[i][j] += d;
}
long long prefix(int x, int y) const { // сумма на [0, x) x [0, y)
long long s = 0;
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j) s += t[i][j];
return s;
}
long long rect(int x1, int y1, int x2, int y2) const { // [x1, x2) x [y1, y2): четыре префиксных запроса
return prefix(x2, y2) - prefix(x1, y2) - prefix(x2, y1) + prefix(x1, y1);
}
};Задача 11. Сумма в прямоугольнике с точечными обновлениями «прибавить $c$ в клетке». Решение: merge sort tree по одной координате и дерево Фенвика по другой — RectSum, $O(\log^2 n)$ на операцию.
// Точки (x, y, c), сумма c в прямоугольнике, значения c иногда меняются. Сами точки не меняются.
// Merge sort tree по x; в каждой вершине — точки, отсортированные по y, и дерево Фенвика по этому порядку. Запрос O(log^2 n), изменение O(log^2 n).
struct RectSum {
struct Pt { int x, y; long long c; int id; };
int n;
vector<Pt> p; // отсортированы по (x, y, id)
vector<vector<pair<int,int>>> ys; // в каждой вершине: пары (y, id) по возрастанию
vector<vector<long long>> fw; // деревья Фенвика над теми же позициями
vector<int> order; // id -> позиция в отсортированном массиве
RectSum(vector<Pt> pts) : n(pts.size()), p(pts), ys(4 * n), fw(4 * n), order(n) {
sort(p.begin(), p.end(), [](const Pt& a, const Pt& b) { return tie(a.x, a.y, a.id) < tie(b.x, b.y, b.id); });
for (int i = 0; i < n; i++) order[p[i].id] = i;
build(1, 0, n);
}
void build(int v, int l, int r) {
for (int i = l; i < r; i++) ys[v].push_back({p[i].y, p[i].id});
sort(ys[v].begin(), ys[v].end());
fw[v].assign(ys[v].size() + 1, 0);
for (size_t k = 0; k < ys[v].size(); k++) fenAdd(v, k, p[order[ys[v][k].second]].c);
if (r - l == 1) return;
int mid = (l + r) / 2;
build(2 * v, l, mid); build(2 * v + 1, mid, r);
}
void fenAdd(int v, int k, long long d) { for (k++; k < (int)fw[v].size(); k += k & -k) fw[v][k] += d; }
long long fenSum(int v, int k) const { long long s = 0; for (; k > 0; k -= k & -k) s += fw[v][k]; return s; } // сумма первых k
void update(int id, long long delta) { // прибавить delta к c точки id
int pos = order[id];
updateRec(1, 0, n, pos, p[pos].y, id, delta);
p[pos].c += delta;
}
void updateRec(int v, int l, int r, int pos, int y, int id, long long d) {
int k = lower_bound(ys[v].begin(), ys[v].end(), make_pair(y, id)) - ys[v].begin();
fenAdd(v, k, d);
if (r - l == 1) return;
int mid = (l + r) / 2;
if (pos < mid) updateRec(2 * v, l, mid, pos, y, id, d); else updateRec(2 * v + 1, mid, r, pos, y, id, d);
}
// сумма по точкам с x in [x1, x2), y in [y1, y2)
long long query(int x1, int x2, int y1, int y2) {
int l = lower_bound(p.begin(), p.end(), x1, [](const Pt& a, int x) { return a.x < x; }) - p.begin();
int r = lower_bound(p.begin(), p.end(), x2, [](const Pt& a, int x) { return a.x < x; }) - p.begin();
return rec(1, 0, n, l, r, y1, y2);
}
long long rec(int v, int l, int r, int ql, int qr, int y1, int y2) const {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) { // вершина целиком: два бинпоиска по y и два запроса к Фенвику
int a = lower_bound(ys[v].begin(), ys[v].end(), make_pair(y1, INT_MIN)) - ys[v].begin();
int b = lower_bound(ys[v].begin(), ys[v].end(), make_pair(y2, INT_MIN)) - ys[v].begin();
return fenSum(v, b) - fenSum(v, a);
}
int mid = (l + r) / 2;
return rec(2 * v, l, mid, ql, qr, y1, y2) + rec(2 * v + 1, mid, r, ql, qr, y1, y2);
}
};Задача 12. Минимум в прямоугольнике.
Многое, ради чего пишут декартово дерево, уже есть в std::set. Итераторы — «указатели» на элементы множества: begin() — минимум, end() — «после последнего», rbegin()/rend() — обратный обход, next/prev — сдвиг на шаг. prev(end()) — максимум.
ordered_set из pb_ds (find_by_order, order_of_key).s.lower_bound(x) работает за $O(\log n)$, а общая std::lower_bound(s.begin(), s.end(), x) — за $O(n)$, потому что итераторы множества не произвольного доступа. Это исправление неточности в записи: при замере на большом множестве метод отработал порядка 1,5 мс, а общая функция — порядка 4,4 с.prev(s.lower_bound(x)) — но с проверкой lower_bound != begin().Почему set — красно-чёрное дерево, а не декартово? Красно-чёрное даёт детерминированные и неамортизированные $O(\log n)$ — лучшие гарантии, чем у случайной структуры. Итераторы остаются корректными при вставках и удалениях других элементов.
// k-й минимум во множестве (k фиксировано): держим итератор на k-й элемент. Элементы различны.
struct KthMin {
set<int> s;
int k;
set<int>::iterator it; // указывает на k-й минимум, если |s| >= k
KthMin(int k) : k(k), it(s.end()) {}
void add(int x) {
s.insert(x);
if ((int)s.size() == k) it = prev(s.end()); // впервые набрали k элементов
else if ((int)s.size() > k && x < *it) --it; // новый меньше — k-й сдвигается влево
}
void erase(int x) {
if ((int)s.size() >= k) {
if (x > *it) {} // удаляем правее — итератор не меняется
else if (x == *it) { if ((int)s.size() > k) ++it; else it = s.end(); } // сначала сдвигаем итератор, потом удаляем
else if ((int)s.size() > k) ++it; // левее — k-й сдвигается вправо
else it = s.end(); // элементов станет меньше k
}
s.erase(x);
}
int get() const { return (int)s.size() >= k ? *it : -1; }
};
// медиана (элемент с номером (n+1)/2 по возрастанию, n = |s|) при добавлениях и удалениях: итератор сдвигается не более чем на 1
struct Median {
set<int> s;
set<int>::iterator it = s.end();
void add(int x) {
size_t n = s.size(); // размер до вставки
if (n == 0) { it = s.insert(x).first; return; }
int med = *it;
s.insert(x); // итератор it остаётся валидным и указывает на прежнюю медиану
if (n % 2 == 0) { if (x > med) ++it; } // номер медианы вырос на 1, а новый элемент правее — берём следующего
else { if (x < med) --it; } // номер не изменился, но новый элемент левее — медиана сдвинулась на предыдущего
}
void erase(int x) {
size_t n = s.size(); // размер до удаления
if (n == 1) { s.erase(x); it = s.end(); return; }
int med = *it;
if (x == med) { // удаляем саму медиану: сначала сдвигаем итератор
auto nx = (n % 2 == 1) ? prev(it) : next(it);
s.erase(x); it = nx;
} else if (x < med) { s.erase(x); if (n % 2 == 0) ++it; }
else { s.erase(x); if (n % 2 == 1) --it; }
}
int get() const { return *it; }
};198:23 Задача. Дан массив $a$ и запросы $[L,R)$. Для каждого запроса найти сумму минимумов всех подотрезков $[l,r)\subseteq[L,R)$.
Первый подход (пробивной). Для каждого элемента найти, на скольких подотрезках он минимум — через стек ближайших меньших слева и справа; получаем ответ на весь массив за $O(n)$, но запросы на $[L,R)$ так не решаются быстро.
Основной способ — сканлайн по правой границе. Идём $r=1,2,\dots,n$. Храним массив $M[i]=\min(a[i..r])$ и массив $S[i]$ — историческую сумму: сумму значений $M[i]$ по всем уже пройденным версиям. Тогда после шага $r$ значение $S[i]=\sum_{r'\le r}\min(a[i..r'])$, а ответ на запрос $[L,R)$, закончившийся в $R$, — сумма $S$ на $[L,R)$.
Переход $r\to r+1$ : по стеку минимумов находим отрезки, где $M$ надо заменить на $a_r$ (присваивание на отрезке), затем делаем «$S\mathrel{+}=M$» на всём массиве. Всего $O(n)$ присваиваний, итого $O(n+q)\log n$.
Как реализовать ленивые операции? Операция над вершиной (парой «значение $M$, историческая сумма $S$») задаётся четвёркой: $$S'=S+\alpha M+\beta,\qquad M'=\gamma M+\delta .$$ Присваивание $M=c$ — это $(0,0,0,c)$ (сумма $S$ не меняется, $M$ заменяется на $c$). «Прибавить $M$ к $S$» — $(1,0,1,0)$. Композиция: сначала $(\alpha_1,\beta_1,\gamma_1,\delta_1)$, затем $(\alpha_2,\beta_2,\gamma_2,\delta_2)$: $$\alpha=\alpha_1+\alpha_2\gamma_1,\quad\beta=\beta_1+\alpha_2\delta_1+\beta_2,\quad\gamma=\gamma_2\gamma_1,\quad\delta=\gamma_2\delta_1+\delta_2.$$ Это перемножение матриц $3\times3$ над вектором $(S,M,1)$: $$\begin{pmatrix}S'\\M'\\1\end{pmatrix}=\begin{pmatrix}1&\alpha&\beta\\0&\gamma&\delta\\0&0&1\end{pmatrix}\begin{pmatrix}S\\M\\1\end{pmatrix}.$$ Ассоциативность композиции гарантируется матричной записью. Длина отрезка при применении: $S$ суммируется по вершине, поэтому в формуле надо учитывать размер отрезка (слагаемое $\beta$ умножается на длину).
// Историческое дерево отрезков: сумма минимумов по всем подотрезкам [L, R) — offline, сканлайн по правому концу.
// M[i] = min(a[i..r]) для i <= r (иначе 0), S[i] = сумма M[i] по всем «версиям» (моментам r). Ответ на запрос: sum S[L..R-1] в момент r = R-1.
// Модификатор (al, be, ga, de) превращает пару (S, M) элемента в (S + al*M + be, ga*M + de).
typedef long long ll;
struct Mod {
ll al = 0, be = 0, ga = 1, de = 0; // по умолчанию — тождественный
bool isId() const { return al == 0 && be == 0 && ga == 1 && de == 0; }
};
Mod compose(const Mod& f, const Mod& g) { // сначала f, потом g
Mod h;
h.al = f.al + g.al * f.ga;
h.be = f.be + g.al * f.de + g.be;
h.ga = g.ga * f.ga;
h.de = g.ga * f.de + g.de;
return h;
}
struct HistTree {
int n;
vector<ll> sumS, sumM;
vector<Mod> tag;
HistTree(int n) : n(n), sumS(4 * n, 0), sumM(4 * n, 0), tag(4 * n) {}
void applyTo(int v, int len, const Mod& m) { // применить модификатор к целой вершине длины len
sumS[v] += m.al * sumM[v] + m.be * len;
sumM[v] = m.ga * sumM[v] + m.de * len;
tag[v] = compose(tag[v], m);
}
void push(int v, int l, int r) {
if (tag[v].isId()) return;
int mid = (l + r) / 2;
applyTo(2 * v, mid - l, tag[v]);
applyTo(2 * v + 1, r - mid, tag[v]);
tag[v] = Mod();
}
void update(int v, int l, int r, int ql, int qr, const Mod& m) { // [ql, qr)
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { applyTo(v, r - l, m); return; }
push(v, l, r);
int mid = (l + r) / 2;
update(2 * v, l, mid, ql, qr, m); update(2 * v + 1, mid, r, ql, qr, m);
sumS[v] = sumS[2 * v] + sumS[2 * v + 1]; sumM[v] = sumM[2 * v] + sumM[2 * v + 1];
}
ll querySumS(int v, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return sumS[v];
push(v, l, r);
int mid = (l + r) / 2;
return querySumS(2 * v, l, mid, ql, qr) + querySumS(2 * v + 1, mid, r, ql, qr);
}
};
// запросы (L, R) — полуинтервалы; ответ — сумма минимумов всех подотрезков a[L..R)
vector<ll> sumOfMinimums(const vector<int>& a, const vector<pair<int,int>>& qs) {
int n = a.size();
vector<vector<int>> byR(n + 1);
for (size_t i = 0; i < qs.size(); i++) byR[qs[i].second].push_back(i);
vector<ll> ans(qs.size());
HistTree T(n);
vector<int> st; // стек индексов: значения возрастают
for (int r = 0; r < n; r++) {
while (!st.empty() && a[st.back()] >= a[r]) st.pop_back();
int left = st.empty() ? 0 : st.back() + 1; // для i in [left, r] минимум на [i, r] равен a[r]
st.push_back(r);
Mod assign; assign.al = 0; assign.be = 0; assign.ga = 0; assign.de = a[r]; // M := a[r] на отрезке [left, r]
T.update(1, 0, n, left, r + 1, assign);
Mod accumulate; accumulate.al = 1; accumulate.be = 0; accumulate.ga = 1; accumulate.de = 0; // S += M (для всех позиций)
T.update(1, 0, n, 0, n, accumulate);
for (int qi : byR[r + 1]) ans[qi] = T.querySumS(1, 0, n, qs[qi].first, qs[qi].second);
}
return ans;
}Проверка. Код сравнивался с перебором за $O(n^3)$ на случайных массивах малого размера, расхождений не было.
245:07 Ниже — только идеи решений, как их рассказывал лектор (условия восстановлены по обсуждению и могут отличаться деталями от оригинала). Код приведён только для одной задачи (H).
Нужно работать в целых числах: пересечение отрезков и расстояния до отрезков сводятся к знаку векторного произведения и скалярным произведениям. Луч заменяется достаточно длинным отрезком — так не приходится писать отдельные случаи.
Классическая задача на пересечение окружностей: по расстоянию между центрами и радиусам определяется число общих точек (вне, касание, пересечение, вложение). Точки пересечения находятся через проекцию на линию центров.
Кратчайший путь из $A$ в $B$, не заходя внутрь круга. Если отрезок $AB$ не пересекает круг — длина $|AB|$. Иначе путь = касательная из $A$ + дуга окружности + касательная к $B$; перебираем 4 варианта выбора пары касательных и берём минимальный.
За $O(\log n)$: фиксируем вершину $p_0$, бинпоиском по углу находим сектор $p_0p_ip_{i+1}$, содержащий точку, и проверяем попадание в треугольник.
Лежат ли точки по разные стороны от прямой? Строим выпуклую оболочку и ищем на ней две касательные, параллельные данной прямой (крайние точки в направлении нормали); проверяем знаки.
При удалении точки меняют оболочку только её вершины; для каждой вершины оболочки считаем, сколько точек появится на новой оболочке — кандидаты лежат в секторе между соседними вершинами. Итог $O(n\log n)$.
Среди первых пяти точек по принципу Дирихле три лежат на одной окружности; перебираем $\binom53=10$ кандидатов, для каждого проверяем остальные точки за $O(n)$.
Дана строка поворотов L/R; надо построить несамопересекающуюся ломаную с такими поворотами. Идея — адаптированный «заворачивающийся подарок» (Джарвис): на каждом шаге из ещё не использованных точек берём самую левую (для L) или самую правую (для R) относительно текущего направления. $O(n^2)$.
// Ломаная по точкам общего положения с заданной строкой поворотов s (длина n - 2, 'L' — левый, 'R' — правый).
// Адаптированное заворачивание подарка: на i-м шаге идём в такую точку, что все оставшиеся лежат слева (если s[i] = 'L') или справа.
struct P { long long x, y; };
long long cross(P a, P b, P c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); }
vector<int> turnPolyline(const vector<P>& p, const string& s) {
int n = p.size();
vector<bool> used(n, false);
int cur = 0;
for (int i = 1; i < n; i++) // начинаем с самой левой (затем нижней) точки — она на выпуклой оболочке
if (p[i].x < p[cur].x || (p[i].x == p[cur].x && p[i].y < p[cur].y)) cur = i;
vector<int> order = {cur};
used[cur] = true;
for (int i = 0; i < n - 2; i++) {
int best = -1;
for (int j = 0; j < n; j++) {
if (used[j]) continue;
// 'L': нужна точка, левее которой нет остальных, то есть «самая правая по углу»; 'R' — наоборот
if (best < 0) best = j;
else {
long long c = cross(p[cur], p[best], p[j]); // > 0: j левее вектора cur->best
if (s[i] == 'L' ? c < 0 : c > 0) best = j; // для 'L' заменяем best на j, если j правее
}
}
used[best] = true; order.push_back(best); cur = best;
}
for (int j = 0; j < n; j++) if (!used[j]) order.push_back(j); // последняя оставшаяся точка
return order;
}Проверка: построенные ломаные сверялись на отсутствие самопересечений и корректность поворотов на случайных тестах.
Деревья — круги; пройти нельзя, если цепочка кругов (расширенных на радиус человека) соединяет границы. Бинарный поиск по $K$ из запросов и DFS по графу пересекающихся кругов.
Для каждой пары условие «расстояние до отрезка $\le R$ при всех $k$» превращается в пересечение множества допустимых направлений: для каждого $k$ получаем луч и дугу углов, дуги пересекаем. Итого $O(n^2)$.