0:51 Стандартная нумерация «сверху» — с нуля: корень $0$, левый сын $2v+1$, правый $2v+2$. Нумерация с единицы (корень $1$, левый сын $2v$, правый $2v+1$, предок $\lfloor v/2\rfloor$) удобнее. Главное — чтобы все в команде писали одинаково. Для такого дерева нужно $4n$ памяти (или $2n$, если $n$ — степень двойки); существуют нумерации «в порядке обхода», которым нужно ровно $2n$ ячеек, но отлаживать их неприятно.
2:14 Ниже разбирается дерево отрезков снизу (нерекурсивное), которое всегда занимает ровно $2n$ ячеек, а затем — как с ним работать при $n$, не равном степени двойки.
2:54 Сначала считаем, что $n$ — степень двойки. Корень — вершина $1$, листья — вершины $n,\dots,2n-1$ (лист $i$ стоит в ячейке $n+i$), у вершины $v$ сыновья $2v$ и $2v+1$, предок — $\lfloor v/2\rfloor$.
vector<long long> t(2 * n);
for (int i = 0; i < n; ++i) t[n + i] = a[i]; // листья
for (int i = n - 1; i >= 1; --i) t[i] = t[2*i] + t[2*i + 1]; // внутренние вершины5:02 Построение — четыре строки и намного быстрее, чем сверху: оба цикла идут подряд по памяти (два слоя параллельно), что хорошо работает с кэшем.
7:02 Вместо спуска от корня поднимаемся от листьев. Отрезок $[l,r)$ в листьях — это $[l+n, r+n)$. На каждом уровне: если левая граница $l$ нечётна, то вершина $l$ — правый сын, её предок захватил бы лишнее слева, поэтому берём саму вершину $l$ и сдвигаем $l$ вправо ($l{+}{+}$). Если правая граница $r$ нечётна, то вершина $r-1$ — левый сын, берём её ($--r$). Затем поднимаемся на уровень выше: $l\gg=1$, $r\gg=1$. Так мы всегда учитываем значение в самой высокой вершине, которая целиком лежит в запросе.
long long get(int l, int r) { // сумма на [l, r)
long long res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++]; // l — правый сын: берём его
if (r & 1) res += t[--r]; // r-1 — левый сын: берём его
}
return res;
}13:12 Время работы — $O(\log(r-l))$, а не просто $O(\log n)$: у запроса из одного элемента получится одна-две итерации. Поэтому на практике снизу часто работает ощутимо быстрее, чем сверху (особенно при большом числе коротких запросов).
14:33 Верхние оценки: цикл поднимается не выше уровня, где границы совпадут; число уровней — $O(\log (r-l))$.
16:35 Меняется только путь от листа к корню:
void update(int p, long long x) {
p += n;
t[p] = x;
while (p > 1) { p >>= 1; t[p] = t[2*p] + t[2*p + 1]; }
}19:19 Те вершины, которые в запросе суммы мы «добавляли к ответу», теперь изменяем сами: храним в вершине не сумму, а модификатор (прибавку ко всем листьям поддерева). Запрос «значение в точке» — сумма модификаторов на пути от листа до корня.
vector<long long> d(2 * n, 0);
void add(int l, int r, long long x) { // a[i] += x для i в [l, r)
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) d[l++] += x;
if (r & 1) d[--r] += x;
}
}
long long getPoint(int p) { // значение a[p]
long long s = 0;
for (p += n; p >= 1; p >>= 1) s += d[p];
return s;
}22:19 Просто повторить трюк не выйдет: если хранить массив сумм и массив модификаторов, то при запросе суммы мы на самом нижнем уровне берём значения, но не учитываем модификаторы, лежащие выше. Нужно «протолкнуть» (push) модификаторы сверху вниз по левому и правому пути до листьев запроса: push по вершинам $l\gg i$ и $(r-1)\gg i$ для $i$ от высоты до $1$. Затем выполняется обычный код запроса. Для обновления после изменения нужно ещё и пересчитать значения на путях (build).
// n — любое, h = высота: h = 32 - __builtin_clz(n)
vector<long long> t(2 * n), d(n); // t — суммы, d — отложенные прибавки внутренних вершин
void apply(int p, long long v, int k) { // k — длина отрезка вершины p
t[p] += v * k;
if (p < n) d[p] += v;
}
void build(int p) { // пересчитать предков листа p
for (int k = 1; p > 1; ) {
p >>= 1; k <<= 1;
t[p] = t[2*p] + t[2*p + 1] + d[p] * k;
}
}
void push(int p) { // протолкнуть сверху вниз путь к листу p
for (int s = h, k = 1 << (h - 1); s > 0; --s, k >>= 1) {
int i = p >> s;
if (d[i]) { apply(2*i, d[i], k); apply(2*i + 1, d[i], k); d[i] = 0; }
}
}
void add(int l, int r, long long v) {
l += n; r += n;
int l0 = l, r0 = r, k = 1;
for (; l < r; l >>= 1, r >>= 1, k <<= 1) {
if (l & 1) apply(l++, v, k);
if (r & 1) apply(--r, v, k);
}
build(l0); build(r0 - 1);
}
long long get(int l, int r) {
l += n; r += n;
push(l); push(r - 1);
long long res = 0;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += t[l++];
if (r & 1) res += t[--r];
}
return res;
}push показывалась идея сдвигов $L\gg i$ и $(R-1)\gg i$ («нас интересует всё, что влияет на последнюю вершину ответа»); остальная часть кода — полная версия этой идеи.25:07 Дерево снизу легко делается двумерным: запрос $[l_x,r_x)\times[l_y,r_y)$ — это два вложенных цикла «снизу вверх», по $x$ и по $y$; внутри обращаемся к ячейке f[lx][ly] и учитываем её, только если соответствующие границы нечётны. Сложность $O(\log n\cdot\log m)$.
29:10 Дополнять массив до степени двойки не обязательно: описанный код работает и для любого $n$. Разберём $n=6$. Листья — вершины $6,\dots,11$ (ровно $n$ штук, идут подряд, лист $i$ — в ячейке $n+i$). Но если нарисовать дерево по правилу «сыновья $v$ — $2v$ и $2v+1$», листья $6,7$ (индексы $0,1$) оказываются на уровень выше листьев $8,\dots,11$ (индексы $2,\dots,5$) и на картинке стоят «неправильно» — правее. Это только вопрос рисунка.
30:31 Перерисуем: вырежем «неправильную» часть и подвинем направо на слой выше. Теперь картинка обладает всеми нужными свойствами: листья идут подряд, сыновья $v$ — $2v$ и $2v+1$, к следующей вершине слоя переходим прибавлением единицы. Больше никакими свойствами алгоритмы не пользуются, поэтому запросы работают. Дерево при этом состоит из нескольких «склеенных» полных деревьев (вершина $1$ может быть «лишней»), и запрос разбивается на вершины из разных таких деревьев.
35:20 Операция $\circ$ коммутативна, если $a\circ b=b\circ a$ (сумма, минимум, максимум, xor …), и ассоциативна, если $(a\circ b)\circ c=a\circ(b\circ c)$. Для матриц умножение ассоциативно, но не коммутативно. Запрос в дереве сверху при ассоциативной операции работает всегда (сначала левая часть, потом правая). В нашем коде снизу нужно хранить два аккумулятора: resl для левых вершин и resr для правых, и объединить их в конце:
T get(int l, int r) {
T resl = e, resr = e; // e — нейтральный элемент
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) resl = op(resl, t[l++]); // левая часть растёт вправо
if (r & 1) resr = op(t[--r], resr); // правая часть растёт влево
}
return op(resl, resr);
}38:09 Структура остаётся корректной и для других «неудобных» $n$ (например, $n=7$: появляются дополнительные вершины, часть дерева «склеена» из нескольких полных деревьев) — все запросы работают так же, число вершин в разбиении запроса по-прежнему $O(\log n)$.
40:14 Массив t[1..n] (нулевой элемент не используем). Две операции: прибавить $x$ в точке и найти сумму на префиксе. Хранится в t[i] сумма элементов $a_{i-\mathrm{lowbit}(i)+1},\dots,a_i$, где $\mathrm{lowbit}(i)=i\,\&\,(-i)$ — младший единичный бит.
vector<long long> t(n + 1, 0);
void add(int i, long long x) { // a[i] += x, i в 1..n
for (; i <= n; i += i & -i) t[i] += x;
}
long long prefix(int i) { // сумма a[1..i]
long long s = 0;
for (; i > 0; i -= i & -i) s += t[i];
return s;
}
// сумма на [l, r] = prefix(r) - prefix(l - 1)t[i] отвечает за $(i-\mathrm{lowbit}(i),\,i]$. Например, $t_6$ покрывает $a_5,a_6$, а $t_8$ — всё $[1,8]$.44:31 Отрицательные числа хранятся в дополнительном коде: $-x$ — это побитовое отрицание $x$ плюс единица. Пусть $x$ имеет вид «что-то, затем единица, затем $k$ нулей». После отрицания «что-то» меняется на противоположное, единица становится нулём, а $k$ нулей — единицами; при прибавлении единицы все эти единицы дают перенос, выжимающий нуль в единицу на месте исходной единицы. Итого $x\,\&\,(-x)$ оставляет ровно одну исходную единицу — младший бит. Например, для $20=10100_2$ получается $4$.
50:43 Двумерное дерево Фенвика пишется ещё проще — просто два вложенных цикла (по $i$ и по $j$).
52:47 Пусть дана матрица (пока $n\le 1000$), запросы: прибавить в точке и найти сумму на подпрямоугольнике. Строим дерево отрезков по первой координате; каждая вершина (отрезок $[a,b)$ по $x$) хранит внутреннее дерево по $y$, в $j$-й позиции которого лежит сумма в «столбце» $\{(i,j): i\in[a,b)\}$. Обновление: спускаемся по внешнему дереву ($O(\log)$ вершин, содержащих точку) и в каждой обновляем внутреннее дерево. Запрос: раскладываем отрезок по $x$ в $O(\log)$ вершин и в каждой делаем запрос по $y$. Итого $O(\log^2)$ на операцию.
55:30 При $n=1000$ это очень быстро и по памяти ($n\times m$ ячеек). Но если матрица огромная (например, $10^5\times10^5$), хранить её нельзя.
lower_bound. Память — $O(n\log n)$, время всё ещё $O(\log^2)$.62:20 Присваивание на прямоугольнике с суммой на прямоугольнике в лекции оставлено домашним заданием; рассмотрим «прибавить на прямоугольнике, сумма на прямоугольнике».
63:42 Сумму на прямоугольнике сводим к четырём суммам на префиксах (включения–исключения, как в префиксных суммах). Значит, нужно научиться: прибавить на прямоугольнике, узнать сумму на префиксе $[0,X]\times[0,Y]$. Если $a$ прибавлено на прямоугольнике с левым верхним углом $(x_0,y_0)$, то в точках $(X,Y)$ внутри «правой нижней» области префиксная сумма увеличивается на $a\,(X-x_0+1)(Y-y_0+1)$ — билинейная функция от $(X,Y)$. Раскрыв скобки, получаем линейную комбинацию $XY,\ X,\ Y,\ 1$ с коэффициентами, зависящими только от $a,x_0,y_0$:
65:07 Поэтому в каждой точке храним вектор из четырёх коэффициентов, при прибавлении на прямоугольнике прибавляем соответствующие векторы на четырёх областях (на трёх остальных они проще — зависят только от $Y$ или только от $X$), а при запросе берём вектор в точке и домножаем на $(XY,X,Y,1)$. Нужна структура «прибавление на прямоугольнике — значение в точке», а её, в отличие от суммы, можно сделать просто (двумерное дерево, как «прибавить на отрезке — значение в точке»).
67:11 Эквивалентная реализация без деревьев отрезков: 2D дерево Фенвика с четырьмя массивами. Если $D$ — двумерный разностный массив (прибавление $v$ на прямоугольнике — это четыре прибавления $\pm v$ в точках-углах), то префиксная сумма в точке $(x,y)$ равна
// 4 двумерных дерева Фенвика a0..a3 (индексы с 1)
void point(int x, int y, long long v) { // D[x][y] += v
upd(a0, x, y, v); upd(a1, x, y, v * x);
upd(a2, x, y, v * y); upd(a3, x, y, v * x * y);
}
void addRect(int x1, int y1, int x2, int y2, long long v) { // + v на [x1..x2] x [y1..y2]
point(x1, y1, v); point(x1, y2 + 1, -v);
point(x2 + 1, y1, -v); point(x2 + 1, y2 + 1, v);
}
long long pref(int x, int y) {
return (long long)(x + 1) * (y + 1) * qry(a0, x, y) - (long long)(y + 1) * qry(a1, x, y)
- (long long)(x + 1) * qry(a2, x, y) + qry(a3, x, y);
}
long long sumRect(int x1, int y1, int x2, int y2) {
return pref(x2, y2) - pref(x1 - 1, y2) - pref(x2, y1 - 1) + pref(x1 - 1, y1 - 1);
}68:40 Почему нельзя «в лоб» сделать прибавление на прямоугольнике и сумму на прямоугольнике двумерным деревом отрезков: прибавив на отрезке внешнего дерева, нужно «толкнуть» отложенную операцию детям, но у каждой вершины внешнего дерева — целое внутреннее дерево, и «толкнуть дерево в два других дерева» нельзя.
72:13 Sparse table для минимума отвечает на запрос двумя пересекающимися отрезками, что допустимо лишь для идемпотентных операций (минимум). Нужна структура, которая разбивает любой отрезок на два непересекающихся отрезка из заранее хранимого набора — для произвольных ассоциативных операций.
80:31 Дополняем $n$ до степени двойки. На уровне $h$ массив разбит на блоки длины $2^{h+1}$ с серединой $m$; для $i$ из левой половины храним агрегат на $[i,m)$, для $i$ из правой — агрегат на $[m,i]$. Запрос $[l,r]$ ($l\ne r$): нужный уровень — это номер старшего бита числа $l\oplus r$ (на этом уровне $l$ и $r$ в разных половинах одного блока); ответ — t[h][l] $\circ$ t[h][r].
// n — степень двойки, LOG = log2(n)
vector<vector<long long>> t(LOG, vector<long long>(n));
for (int h = 0; h < LOG; ++h) {
int blk = 1 << (h + 1), half = 1 << h;
for (int s = 0; s < n; s += blk) {
int mid = s + half;
t[h][mid - 1] = a[mid - 1];
for (int i = mid - 2; i >= s; --i) t[h][i] = t[h][i + 1] + a[i]; // [i, mid)
t[h][mid] = a[mid];
for (int i = mid + 1; i < s + blk; ++i) t[h][i] = t[h][i - 1] + a[i]; // [mid, i]
}
}
long long query(int l, int r) { // сумма на [l, r] (включительно)
if (l == r) return a[l];
int h = 31 - __builtin_clz(l ^ r); // старший бит l xor r
return t[h][l] + t[h][r];
}__builtin_clz__lg(x) — то же самое, «логарифм по основанию 2, округлённый вниз»). Участники обсуждали, какая из записей быстрее; на это можно не обращать внимания, главное — что обе дают номер старшего бита. Код проверен на случайных массивах: ответы совпадают с суммированием для всех отрезков.74:15 Дан неизменный массив цен $a_1,\dots,a_n$. Запрос $(l,r)$: торгуем на этом подотрезке, храним не более одной картошки; можно купить за $a_i$ (если картошки нет) или продать за $a_i$ (если есть); сделок не более $k$ (например, $k\le 50$). Найти максимальную прибыль.
77:02 В дереве отрезков в вершине хранить динамику «сколько сделок сделано, была ли картошка в начале, будет ли в конце» — склейка за $O(k^2)$ (или за $O(k)$ при слиянии «не более $x$»), что даёт $O(k\log n)$–$O(k^2\log n)$ на запрос. Лучше так (оффлайн-идея): разделить массив пополам, для всех отрезков, пересекающих середину, ответ получается слиянием двух динамик — «слева от середины» и «справа от середины». Те же динамики можно сохранить для всех уровней разбиения — получается disjoint sparse table, где в качестве «агрегата» используется ДП по числу сделок.
78:24 Слияние двух ДП за $O(k)$: пусть «$x$» — не более $x$ сделок; в первой ДП перебираем, сколько сделок сделано, во второй берём $k-x$. Пересчёт ДП при добавлении одной цены также за $O(k)$.
84:48 Нужна структура, поддерживающая set (вставка, удаление, поиск) быстро. Стандартное средство — бинарное дерево поиска: у каждой вершины ключ $x$, в левом поддереве все ключи меньше, в правом — больше. Обход «левое поддерево, вершина, правое поддерево» (in-order) выдаёт упорядоченный массив. Беда — балансировка.
86:48 Декартово дерево (treap) = tree + heap: у каждой вершины есть ещё случайный приоритет $y$; по ключу $x$ дерево — бинарное дерево поиска, по приоритету $y$ — куча (в корне минимум). При различных приоритетах такое дерево с заданными парами $(x,y)$ единственно.
88:19 Все операции выражаются через две вспомогательные. merge(A, B) — сливает два дерева, все ключи в $A$ меньше всех в $B$; корень — тот из корней с меньшим приоритетом:
struct Node { int l = 0, r = 0, sz = 1; unsigned pr; int val; }; // 0 — «пустая» вершина
int merge(int a, int b) {
if (!a) return b;
if (!b) return a;
if (t[a].pr < t[b].pr) { t[a].r = merge(t[a].r, b); upd(a); return a; }
t[b].l = merge(a, t[b].l); upd(b); return b;
}90:28 split(v, x) — разделяет дерево на пару: ключи меньше $x$ и остальные. Если корень идёт влево, то всё его левое поддерево идёт влево, а правое поддерево делится рекурсивно; симметрично, если корень идёт вправо.
pair<int,int> split(int v, int x) { // (ключи < x, ключи >= x)
if (!v) return {0, 0};
if (key[v] < x) { // корень уходит влево
auto [l, r] = split(t[v].r, x);
t[v].r = l; upd(v); return {v, r};
}
auto [l, r] = split(t[v].l, x); // корень уходит вправо
t[v].l = r; upd(v); return {l, v};
}93:54 Каждая операция работает за глубину вершины, а глубину можно записать как число предков: $E[\text{глубина}(v)]=\sum_u P(u\text{ — предок }v)$. Вершина $u$ является предком $v$ тогда и только тогда, когда у $u$ наименьший приоритет среди всех вершин между $u$ и $v$ включительно (иначе между ними нашлась бы вершина с меньшим приоритетом, которая «разделила» бы их). Если ключи — числа $0,\dots,n-1$, вероятность этого равна $\dfrac{1}{|u-v|+1}$. Сумма по всем $u$ — две ветви гармонического ряда:
95:28 Итого все операции работают за $O(\log n)$ в среднем (по случайным приоритетам). Условия «$u$ с меньшим приоритетом, чем у $v$» одного недостаточно: нужен минимум именно на всём отрезке между ними.
98:14 Если ключи выбросить, а порядок задавать самим обходом (левое, вершина, правое), получится массив, в который можно вставлять элементы в произвольное место, удалять, вырезать и склеивать куски, разворачивать. merge остаётся прежним; вместо split по ключу вводим split(v, k) — «откусить первые $k$ элементов». Для этого в вершине храним размер поддерева:
pair<int,int> split(int v, int k) { // (первые k элементов, остальные)
if (!v) return {0, 0};
if (sz(t[v].l) + 1 <= k) { // корень в левой части
auto [l, r] = split(t[v].r, k - sz(t[v].l) - 1);
t[v].r = l; upd(v); return {v, r};
}
auto [l, r] = split(t[v].l, k);
t[v].l = r; upd(v); return {l, v};
}
// вставка val на позицию pos:
// auto [l, r] = split(root, pos); root = merge(merge(l, newNode), r);merge/split по размеру) проверено на случайных операциях против vector.100:58 Практический совет с лекции: декартово дерево — рабочая лошадка, но на олимпиаде обычно можно обойтись деревом отрезков; пишите его, когда другого решения действительно нет, но стоит потренироваться и написать несколько раз — тогда оно пишется быстро. Константа у него большая.
103:40 Нужно разбить массив на $k$ отрезков так, чтобы для каждых двух соседних отрезков модуль разности их сумм не превосходил максимума из максимумов в них. Решение (рандомизированное по начальному разбиению): расставить границы случайно; если какие-то границы «плохие», кладём их в очередь. Для границы между двумя блоками берём сумму двух блоков вместе и ставим границу в месте, где префикс переходит через половину суммы — после этого разность сумм не больше максимального элемента. Затем перепроверяем две соседние границы и т. д.
107:08 Идея, почему граница около половины суммы подходит: разность сумм двух частей при сдвиге границы на один элемент меняется не более чем на величину этого элемента, а значит найдётся положение с разностью не больше максимума. Другой взгляд: если минимизировать сумму квадратов сумм отрезков, то для каждой пары соседних отрезков сумма квадратов минимальна, когда суммы почти равны, значит условие выполняется для оптимального разбиения; такие оптимизации можно делать локальными сдвигами границ.
109:54 Есть $n$ символов с частотами $w_i$. Нужно присвоить им двоичные коды, образующие префиксный код, с сохранением порядка (коды возрастают вместе с символами), так, чтобы минимизировать суммарную стоимость $\sum w_i\cdot|c_i|$. Это то же самое, что строить двоичное дерево с листьями в порядке символов. Динамика по отрезкам: $dp_{l,r}$ — минимальная стоимость для символов $l..r$:
111:16 Лишний параметр «длина общего префикса» $x$ можно убрать (он влияет аддитивно — вклад $x\cdot\sum w$). Получаем $O(n^3)$, а так как оптимальное $k$ монотонно (оптимизация Кнута: $opt_{l,r-1}\le opt_{l,r}\le opt_{l+1,r}$), решение работает за $O(n^2)$.
// opt[l][r] — оптимальное k для (l, r); перебор k в [opt[l][r-1], opt[l+1][r]]
for (int len = 2; len <= n; ++len)
for (int l = 0; l + len - 1 < n; ++l) {
int r = l + len - 1; long long best = LLONG_MAX; int bk = -1;
for (int k = opt[l][r - 1]; k <= min(opt[l + 1][r], r - 1); ++k) {
long long v = dp[l][k] + dp[k + 1][r];
if (v < best) { best = v; bk = k; }
}
dp[l][r] = best + (P[r + 1] - P[l]); // P — префиксные суммы w
opt[l][r] = bk;
}112:39 Стек с минимумом: рядом с каждым элементом храним минимум всего стека до него. Очередь из двух стеков: добавляем в первый; извлекаем из второго, а если второй пуст — перекладываем в него все элементы первого.
116:43 Почему операция в среднем $O(1)$ (амортизированно): одна операция может быть долгой, но каждый элемент за свою жизнь участвует не более чем в трёх операциях (добавление, перекладывание, удаление). Через потенциал: потенциал $\Phi=|S_1|$ — размер входного стека. Добавление стоит $1$ и увеличивает $\Phi$ на $1$ — амортизированно $2$. Извлечение без перекладывания стоит $1$ и не меняет $\Phi$. Перекладывание стоит $|S_1|$ (плюс одно извлечение), но обнуляет $\Phi$, то есть уменьшает его ровно на $|S_1|$ — амортизированно $O(1)$. Итого любая операция амортизированно $O(1)$.
121:33 Дано $n$ точек $(x_i,y_i)$, отсортированных по $x$. Построить декартово дерево (в корне минимум $y$) за $O(n)$. Идея: идти слева направо и поддерживать правый путь дерева в стеке. Приходит новая вершина: пока на вершине стека приоритет больше нового, выкидываем её; последний выкинутый становится левым сыном новой вершины, а новая вершина — правым сыном той, что осталась на вершине стека.
vector<int> L(n, -1), R(n, -1), st;
for (int i = 0; i < n; ++i) {
int last = -1;
while (!st.empty() && y[st.back()] > y[i]) { last = st.back(); st.pop_back(); }
L[i] = last; // последний выкинутый — левый сын
if (!st.empty()) R[st.back()] = i; // i — правый сын вершины стека
st.push_back(i);
}
// корень — st[0]122:53 Видно связь с «ближайшим меньшим»: родитель вершины — тот из ближайших слева и справа меньших, у которого приоритет больше.
129:52 В квадрате $C\times C$ разбросаны точки; нужно найти наибольший по стороне квадрат со сторонами, параллельными осям, внутри которого нет точек. Одна идея — бинпоиск по стороне $m$ и проверка «помещается ли квадрат»: «раздуем» каждую точку до запрещённого квадрата и ищем непокрытую точку (сканирующая прямая + дерево отрезков). Вторая идея — два указателя по $x$ и дерево отрезков по $y$, поддерживающее длину наибольшего отрезка без точек для текущего окна по $x$: при расширении окна вправо длина по $x$ растёт, а наибольший пустой промежуток по $y$ не растёт; поэтому, пока ширина окна не превосходит этот промежуток, двигаем правую границу, иначе — левую (монотонность даёт два указателя).
139:25 Массив с изменениями; запрос $(l,r,k)$: верно ли, что каждое число на $[l,r]$ встречается кратное $k$ число раз. Каждому значению сопоставляем случайные числа (50 «хэшей», каждый — 0 или 1). Если все значения встречаются кратно $k$, то для каждого хэша сумма по подотрезку делится на $k$. Если какое-то значение $y$ встречается $c_y\not\equiv0\pmod k$ раз, то его вклад $h(y)\cdot c_y$ ненулевой по модулю $k$ с вероятностью хотя бы $1/2$ (при $h(y)=1$), поэтому один хэш ошибается с вероятностью не более $1/2$, а $50$ независимых — не более $2^{-50}$. Суммы по подотрезку с изменениями — дерево Фенвика на каждый хэш.
153:15 Дан неизменный массив, запросы $(l,r)$: найти mex подотрезка (наименьшее неотрицательное число, которого нет). Идём $r$ слева направо, для каждого значения $x$ храним позицию $last_x$ его последнего вхождения в префиксе (дерево отрезков по значениям на минимум). Для запросов с правой границей $r$ ответ — наименьшее $x$, у которого $last_x<l$: спуск по дереву по минимуму за $O(\log n)$.
156:46 Если в массиве есть изменения в точках, идея другая: для значения $x$ с позициями $p_1<p_2<\dots$ (с добавленными $0$ и $n+1$) mex на $[l,r]$ может быть равен $x$, только если $[l,r]$ лежит строго между двумя соседними позициями $x$: $p<l\le r<p'$. Получаем «тройки» $(p,p',x)$; ищем минимум $x$ среди троек с $p<l$ и $p'>r$ — двумерная задача (дерево по $p$, внутри структура по $p'$ с минимумом по $x$, например декартово дерево или дерево Фенвика со сжатием).
175:10 Даны возрастающий массив $a$ и неотрицательный $b$; запрос $(l,r)$: $\min_{l\le i<j\le r}(b_i+b_j)(a_j-a_i)$. Ключ: в оптимальной (самой короткой) паре $(i,j)$ для каждого $k$ между ними выполнено $b_k>\max(b_i,b_j)$ — иначе пара $(i,k)$ или $(k,j)$ не хуже (сумма $b$ не больше, разность $a$ меньше).
178:40 Значит, кандидаты на пары — для каждого $j$ ближайший слева с $b_i\le b_j$ и для каждого $i$ ближайший справа с $b_j\le b_i$: всего $O(n)$ пар (находятся монотонным стеком). Остаётся двумерная задача: для запросов оффлайн найти минимум значений пар $(i,j)$ с $l\le i$ и $j\le r$ (сортировка по $r$ и дерево Фенвика/отрезков по $i$ на минимум).
187:38 Можно менять местами соседние элементы $x,y$ при условии $x+y\le W$. Построить лексикографически минимальную перестановку. Критерий достижимости: пары элементов, которые нельзя поменять ($x+y>W$), сохраняют относительный порядок, и любая перестановка, их сохраняющая, достижима (доказывается индукцией: «ставим по одному элементу на нужное место свапами»). Итого — найти лексикографически минимальную топологическую сортировку графа с рёбрами между неразменными парами. Но рёбер может быть $O(n^2)$; чтобы сократить, делят числа на «лёгкие» ($2a\le W$ — любые два лёгких меняются) и «тяжёлые» (два тяжёлых никогда не меняются): достаточно рёбер между последовательными тяжёлыми и рёбер от каждой вершины к ближайшему слева и справа элементу, с которым нельзя поменяться.
206:29 Массив цветов, запросы: изменить цвет элемента; узнать минимальное число операций «перекрасить все элементы цвета $a$ в цвет $b$», после которых каждый цвет образует подряд идущий отрезок. Для каждого цвета все позиции между его первым и последним вхождением должны оказаться одного цвета. Рассмотрим «границы» между соседними позициями $i\,|\,i{+}1$; граница вынужденно разрешена (её нельзя делать разноцветной), если она лежит внутри отрезка $[first_c,last_c]$ какого-то цвета $c$. Число цветов в ответе равно числу «свободных» границ плюс один, а число операций — $(\text{число различных цветов}) - (\text{число свободных границ}+1)$.
207:11 Дерево отрезков по границам: для каждого цвета прибавляем $+1$ на отрезке границ внутри его размаха, а свободные границы — это нули; нужно поддерживать «прибавление на отрезке» и «количество нулей» (минимум и число минимумов). Пример: цвета $0,1,1,0,1,3,3,3$ — размахи $0:[0,3]$, $1:[1,4]$, $3:[5,7]$, свободна только граница между позициями $4$ и $5$ — получаем $3-(1+1)=1$ операцию (перекрасить $0$ в $1$).
217:42 У каждой из $n$ карточек три параметра. Одна карточка сильнее другой, если строго лучше хотя бы по двум координатам. Найти карточку, сильнее всех остальных. Решение за $O(n)$: идём по массиву, поддерживая текущего «кандидата»; если новая карточка сильнее кандидата, заменяем им. Затем проверяем, что кандидат действительно сильнее всех. Корректность: если искомая карточка $X$ существует, то, как только она встретится, она станет кандидатом, а никакая более поздняя карточка не может быть сильнее $X$ (она проигрывает $X$ минимум по двум координатам из трёх); до $X$ кандидат заменится на неё. Альтернатива (сложнее): считать xor хэшей «кого карточка превосходит» по каждой паре координат включением–исключением.
224:00 Префиксный рекорд — элемент, строго больший всех предыдущих на отрезке. Запросы: изменение точки и число рекордов на $[l,r]$. В вершине дерева отрезков хранится максимум mx[v] и количество рекордов cnt[v] внутри отрезка вершины. Вспомогательная функция get(v, y) — число рекордов в вершине $v$, если начать с порога $y$ (считаем только элементы $>y$). Пересчёт: cnt[v] = cnt[левый] + get(правый, mx[левый]).
int get(int v, int y) { // число рекордов в поддереве v при пороге y
if (v >= size) return a[v - size] > y; // лист
if (mx[2*v] <= y) return get(2*v + 1, y); // левая половина ничего не даёт
return get(2*v, y) + cnt[v] - cnt[2*v]; // правая часть не изменилась
}
void pull(int v) {
mx[v] = max(mx[2*v], mx[2*v + 1]);
cnt[v] = cnt[2*v] + get(2*v + 1, mx[2*v]);
}
// запрос [l, r]: обходим вершины разбиения слева направо, держим cur — максимум до них:
// ans += get(v, cur); cur = max(cur, mx[v]);226:07 Если $mx[2v]\le y$ — левая половина вообще не даёт рекордов, смотрим только вправо. Иначе максимум левой половины всё равно будет рекордом, а всё правее него по-прежнему определяется тем, что и раньше: для правой части это cnt[v] - cnt[2v], и остаётся только досчитать левую часть. Функция get работает за $O(\log n)$, пересчёт вершины и обновление — $O(\log^2 n)$ (на запрос $O(\log^2n)$).