Занятие проходило в двух форматах. Тем, кто дерево отрезков уже писал, предлагался семинар — разбор идейных задач с короткими «мини-лекциями» внутри, тем, кто видит тему впервые, — обычная лекция. Запись содержит семинар. Для самопроверки перед разделением студентам выдавали тест из семи вопросов; его разбор ниже — это повторение основ, которое нужно перед задачами. Задачи семинара даны листком; в записи условия читаются вслух или пересказываются, поэтому там, где условие не удаётся восстановить, это отмечено. Код ко всем разобранным задачам проверен случайными тестами против прямого вычисления.
59:23 Вопрос 1. За сколько отвечает дерево отрезков на запрос RMQ (минимум на отрезке)? Ответ: $O(\log n)$.
1:00:26 Вопрос 2. В реализации построения при $l+1=r$ (лист) было записано t[v] = a[v], где v — номер вершины. Ошибка: в массиве лежит элемент с индексом l, то есть нужно t[v] = a[l]. Номер вершины и позиция в массиве — разные вещи.
1:00:46 Вопрос 3. Какого размера нужен массив под дерево? Два допустимых ответа: $4n$, либо первая степень двойки, не меньшая $2n$ (то есть $2^{\lceil\log_2 n\rceil+1}$).
1:01:29 Вопрос 4. Пусть $n=2^i$. Куда мы попадаем, перейдя от вершины с номером $v$ к $v+1$? В вершину, которая лежит в том же слое справа от текущей: из отрезка $[l,r)$ — в следующий отрезок той же длины, то есть $[r,\,2r-l)$. Если текущая вершина была последней в слое, то мы попадаем в первую вершину следующего слоя — отрезок в два раза короче, начинающийся с нуля.
1:02:30 Вопрос 5. Индексы сыновей вершины $i$: при нумерации с нуля — $2i+1$ и $2i+2$; при нумерации с единицы — $2i$ и $2i+1$.
1:03:15 Вопрос 6. Дано изменение одного элемента без пересчёта обоих детей: выбираем сторону, в которой лежит позиция. Дерево строится на полуинтервалах $[L,R)$, середина $M=(L+R)/2$. Условие «идти влево» должно быть x < M (а не x <= R и не x <= R/2): в условии из теста было сразу две ошибки — знак сравнения и середина вместо $(L+R)/2$.
1:04:00 Вопрос 7. Дерево отрезков снизу: запрос и обновление идут от листьев вверх по тому же пути, а не от корня вниз. Такая реализация пишется сложнее для нестандартных операций (особенно с массовыми операциями), но работает быстрее — не асимптотически, а по константе.
1:18:35 Общий принцип. Для любой «обычной» задачи на дерево отрезков нужно придумать три вещи: что хранить про отрезок; как склеить ответы для левой и правой половины в ответ для всей вершины; что вернуть для пустого отрезка (аналог нуля для суммы). Тогда build — это склейка снизу вверх, get — склейка ответов в $O(\log n)$ вершинах разбиения запроса, update — изменение листа и серия пересчётов склейкой вдоль пути к корню. Тот же подход, что при поиске динамики: определить состояние, базу и переходы.
1:17:14 Условие. Дан массив, два вида запросов: изменить элемент a[i] = x; для отрезка $[l,r]$ найти наибольшее количество подряд идущих нулей. Второй пункт: на отрезке найти наибольший подотрезок, на котором числа строго возрастают.
1:18:56 Решение (пункт 1). В вершине храним четыре величины: максимальный префикс из нулей pre, максимальный суффикс из нулей suf, максимальную серию нулей внутри best и флаг all («весь отрезок из нулей»); для удобства ещё длину len. База (лист): если элемент ноль, то pre = suf = best = 1, all = true; иначе всё ноль, all = false.
1:20:39 Склейка. Префикс объединённого отрезка — это префикс левой половины, а если левая половина целиком из нулей, то он продолжается в правую: len левой плюс префикс правой. Суффикс симметрично. Лучшая серия — максимум из трёх случаев (1:22:02): серия целиком в левой половине, целиком в правой, либо пересекает границу — тогда она равна суффиксу левой плюс префиксу правой. Флаг all — конъюнкция флагов. Это ровно та же идея, что в задаче о запросах суммы, когда известно, что запрос пересекает середину: ответы для суффиксов левой и префиксов правой частей складываются.
1:25:29 Нейтральный элемент и get. Для пустого отрезка нужен аналог нуля: все счётчики нулевые, но all = true (лектор отмечает «небольшой парадокс»). Тогда get пишется как в сумме: если вершина не пересекается с запросом — возвращаем нейтральный элемент, если целиком внутри — возвращаем сохранённое, иначе склеиваем ответы детей. 1:26:30 update — изменить лист и пересчитать все вершины на пути обратно к корню (последовательность вызовов build для вершин этого пути).
// Узел: самая длинная серия нулей на отрезке. Склейка двух соседних отрезков — «сложение».
struct Node {
int len = 0; // длина отрезка
int pre = 0, suf = 0; // самый длинный префикс / суффикс из нулей
int best = 0; // самая длинная серия нулей внутри
bool all = true; // весь отрезок состоит из нулей
};
Node merge(const Node &a, const Node &b) {
Node r;
r.len = a.len + b.len;
r.pre = a.all ? a.len + b.pre : a.pre; // префикс продолжается в правую часть, если левая вся нулевая
r.suf = b.all ? b.len + a.suf : b.suf;
r.best = max({a.best, b.best, a.suf + b.pre}); // внутри левой, внутри правой или через границу
r.all = a.all && b.all;
return r;
}
Node leaf(int v) { return v == 0 ? Node{1, 1, 1, 1, true} : Node{1, 0, 0, 0, false}; }
const Node NEUTRAL = {0, 0, 0, 0, true}; // «пустой отрезок»: merge(NEUTRAL, x) = x
struct SegTree { // дерево на полуинтервалах [l, r), корень — вершина 1
int n; vector<Node> t;
SegTree(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 (l + 1 == r) { t[v] = leaf(a[l]); return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m, r, a);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
Node get(int v, int l, int r, int ql, int qr) { // [ql, qr)
if (qr <= l || r <= ql) return NEUTRAL;
if (ql <= l && r <= qr) return t[v];
int m = (l + r) / 2;
return merge(get(2 * v, l, m, ql, qr), get(2 * v + 1, m, r, ql, qr));
}
void update(int v, int l, int r, int pos, int val) {
if (l + 1 == r) { t[v] = leaf(val); return; }
int m = (l + r) / 2;
if (pos < m) update(2 * v, l, m, pos, val); else update(2 * v + 1, m, r, pos, val);
t[v] = merge(t[2 * v], t[2 * v + 1]); // пересчёт на обратном пути
}
};1:27:32 Решение (пункт 2): сведение к пункту 1. Пытаться склеивать «возрастающие» префиксы и суффиксы напрямую можно, но получается громоздко: склейка допустима только при условии $a_m<a_{m+1}$ на границе. Проще перейти к разностному массиву знаков: f[i] = 0, если $a_{i+1}>a_i$, и f[i] = 1 иначе. Серия из $k$ нулей в $f$ — это возрастающий подотрезок длины $k+1$. Поэтому ответ для $[l,r]$ — это «серия нулей» на $f[l..r-1]$ плюс один. При изменении $a_i$ меняются не более двух значений $f$ (слева и справа от $i$) — то есть два обычных обновления. Для запроса важно, что при $l=r$ ответ равен 1 (отрезок $f$ пуст).
1:30:59 Условие. Научить дерево отрезков (а) прибавлять число на отрезке и узнавать значение в точке; (б) прибавлять число на отрезке и узнавать сумму на отрезке.
1:32:22 Пункт (а): разностный массив. Будем хранить в дереве (или в любой структуре для сумм на префиксе) не сами элементы, а разности $d_i=a_{i+1}-a_i$. Тогда $a_i=a_1+\sum_{j<i}d_j$ — сумма на префиксе плюс первый элемент (1:33:02: для $a_1$ берём пустой префикс; для $a_2$ — префикс длины 1 и прибавляем $a_1$ и т.д.; всё сокращается). Прибавление $x$ на отрезке $[l,r]$ не меняет разности внутри отрезка, а меняет только две граничные: $d_{l-1}\mathrel{+}=x$, $d_r\mathrel{-}=x$ — два точечных обновления.
1:34:44 Пункт (б): модификатор без проталкивания. Для суммы на отрезке разности не годятся (на каждый элемент нужен отдельный запрос). Трюк: в вершине наряду с суммой хранится модификатор add — сумма всех прибавлений, под которые вершина попала целиком. При обновлении спускаемся как обычно, но когда отрезок вершины целиком внутри запроса, прибавляем $x$ к модификатору и к сумме (на $x\cdot\text{длина}$) и дальше вниз не идём. При пересчёте суммы на обратном пути добавляем $\text{add}[v]\cdot\text{длина}$. При запросе суммы к ответам детей прибавляем add[v] × (число элементов запроса, лежащих под вершиной). Значение в точке — сумма модификаторов по пути от корня плюс значение листа.
Лектор подчёркивает: это не проталкивание (1:37:50): мы ничего не «пушим» вниз; информация лежит на месте, а мы собираем её на обратном пути. Массовые обновления с push — отдельная тема следующей лекции; в этом занятии они запрещены.
// Прибавление на отрезке и сумма на отрезке БЕЗ проталкивания: в вершине храним модификатор add[v]
struct AddSum {
int n; vector<long long> sum, add;
AddSum(int n) : n(n), sum(4 * n, 0), add(4 * n, 0) {}
// sum[v] — настоящая сумма на отрезке вершины (с учётом add[v] и всех модификаторов ниже)
void update(int v, int l, int r, int ql, int qr, long long x) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { add[v] += x; sum[v] += x * (r - l); return; } // отрезок целиком внутри запроса
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m, r, ql, qr, x);
sum[v] = sum[2 * v] + sum[2 * v + 1] + add[v] * (r - l); // add[v] «лежит сверху» над детьми
}
long long get(int v, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return sum[v];
int m = (l + r) / 2;
long long inter = min(r, qr) - max(l, ql); // сколько элементов запроса лежит под вершиной v
return get(2 * v, l, m, ql, qr) + get(2 * v + 1, m, r, ql, qr) + add[v] * inter;
}
};1:41:13 Условие. Массив с точечными изменениями; запрос $[l,r)$: есть ли среди чисел отрезка два равных.
1:41:56 Идея. Дерево отрезков строится не на самих числах, а на вспомогательном массиве $nxt_i$: позиция ближайшего справа такого же числа (или «бесконечность» — удобно $n$, если такого нет). Утверждение: на $[l,r)$ есть два равных ⇔ $\min(nxt_l,\dots,nxt_{r-1})<r$. Доказательство: в каждой позиции $i$ записано число строго больше $i$, поэтому минимум на отрезке $>l$. Если два равных есть, то у левого из ближайшей такой пары $nxt<r$. Обратно, если минимум $<r$, то в позиции с минимумом $nxt_i<r$ и $i\ge l$, то есть пара $(i,nxt_i)$ целиком внутри отрезка.
1:46:07 Обновление. Для каждого значения храним set позиций. Все позиции одного значения образуют односвязный список по возрастанию (каждый указывает на следующего). Замена $a_i$: из списка старого значения вынимаем $i$ — предыдущий равный теперь указывает на следующий после $i$; в список нового значения вставляем $i$ — предыдущий равный нового значения теперь указывает на $i$, а $i$ указывает на следующий. Итого не более трёх точечных обновлений дерева, и каждый поиск соседей в set — $O(\log n)$. Вложенные структуры (map + set + дерево) дают $O(\log n)$, а не $O(\log^2 n)$, потому что операции выполняются последовательно, а не вложенно.
// Есть ли два равных числа на отрезке [l, r)? Храним nxt[i] — позицию следующего равного (или n), дерево на минимум.
struct EqualQuery {
int n, sz; vector<int> a, t; // t — нижний (итеративный) вариант дерева на минимум
map<int, set<int>> pos;
EqualQuery(const vector<int> &arr) : n(arr.size()), a(arr) {
sz = 1; while (sz < n) sz <<= 1;
t.assign(2 * sz, n);
for (int i = 0; i < n; i++) pos[a[i]].insert(i);
for (int i = 0; i < n; i++) setNxt(i);
}
int nxtOf(int i) { auto &s = pos[a[i]]; auto it = s.upper_bound(i); return it == s.end() ? n : *it; }
void setNxt(int i) {
int p = i + sz; t[p] = nxtOf(i);
for (p >>= 1; p; p >>= 1) t[p] = min(t[2 * p], t[2 * p + 1]);
}
void change(int i, int y) { // a[i] = y: «перевешиваем» односвязные списки двух значений
auto &sx = pos[a[i]];
auto it = sx.find(i);
int prv = (it == sx.begin()) ? -1 : *prev(it); // предыдущий равный старому значению
sx.erase(it);
if (prv >= 0) setNxt(prv); // он теперь указывает на следующий после i
a[i] = y;
auto &sy = pos[y];
auto jt = sy.insert(i).first;
if (jt != sy.begin()) setNxt(*prev(jt)); // предыдущий равный новому значению теперь указывает на i
setNxt(i);
}
bool hasEqual(int l, int r) { // минимум nxt на [l, r) должен быть < r
int res = n;
for (int lo = l + sz, hi = r + sz; lo < hi; lo >>= 1, hi >>= 1) {
if (lo & 1) res = min(res, t[lo++]);
if (hi & 1) res = min(res, t[--hi]);
}
return res < r;
}
};1:49:34 Условие (восстановлено по разбору). Клетки в ряд, на каждой записано число монет $v_i$ (могут быть отрицательными). Из клетки можно прыгнуть вправо на 1 или на 2 клетки. Нужно отвечать на запросы: максимально возможная сумма монет на пути из клетки $l$ в клетку $r$; есть изменение $v_i$. Сам текст условия зачитывали в перерыве, поэтому детали (например, нужно ли «ровно из $l$ в $r$») уточняются по разбору.
2:57:47 Идея лектора. Как в задаче про «лунки»: то, что происходит внутри отрезка, снаружи неважно. Для отрезка хранятся четыре числа: максимальный заработок, если путь начинается в одной из первых двух клеток отрезка и заканчивается в одной из последних двух (всего $2\times2$ значения). Склейка двух отрезков: переберём, каким прыжком мы переходим из левого отрезка в правой (на 1 из последней клетки; на 2 из последней или предпоследней клетки в первые две правого), и сложим две «половины пути». Время склейки $O(1)$ (для общего $K$ — $O(K^3)$ или $O(K^2)$ после оптимизации префиксными минимумами). Для отрезков длины 1 нужно аккуратно задать «вырожденные» состояния: невозможные варианты — минус бесконечность.
// Прыжки на 1 или 2 клетки вправо, у клеток «монеты» v[i] (могут быть отрицательными).
// Максимальная сумма пути из l в r. Переход через клетку i: d_i = v_i + max(d_{i-1}, d_{i-2}) — это матрица в полукольце (max, +).
const long long NEG = LLONG_MIN / 4;
struct Mat { // [[a b],[c d]] в (max, +)
long long a, b, c, d;
};
Mat mul(const Mat &x, const Mat &y) { // сначала x, потом y (строка-вектор · x · y); не коммутативно
auto mx = [](long long p, long long q) { return max(max(p, q), NEG); };
return {mx(x.a + y.a, x.b + y.c), mx(x.a + y.b, x.b + y.d),
mx(x.c + y.a, x.d + y.c), mx(x.c + y.b, x.d + y.d)};
}
Mat step(long long v) { return {v, 0, v, NEG}; } // строка (d_{i-1}, d_{i-2}) → (d_i, d_{i-1}): d_i = v + max(d_{i-1}, d_{i-2}), d_{i-1} сохраняется
const Mat ID = {0, NEG, NEG, 0};
struct JumpTree {
int n; vector<Mat> t;
JumpTree(const vector<long long> &v) : n(v.size()), t(4 * v.size()) { build(1, 0, n, v); }
void build(int x, int l, int r, const vector<long long> &v) {
if (l + 1 == r) { t[x] = step(v[l]); return; }
int m = (l + r) / 2; build(2 * x, l, m, v); build(2 * x + 1, m, r, v);
t[x] = mul(t[2 * x], t[2 * x + 1]);
}
Mat get(int x, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return ID;
if (ql <= l && r <= qr) return t[x];
int m = (l + r) / 2; return mul(get(2 * x, l, m, ql, qr), get(2 * x + 1, m, r, ql, qr));
}
void update(int x, int l, int r, int pos, long long val) {
if (l + 1 == r) { t[x] = step(val); return; }
int m = (l + r) / 2; if (pos < m) update(2 * x, l, m, pos, val); else update(2 * x + 1, m, r, pos, val);
t[x] = mul(t[2 * x], t[2 * x + 1]);
}
long long best(const vector<long long> &v, int l, int r) { // путь из клетки l в клетку r (l <= r)
if (l == r) return v[l];
Mat M = get(1, 0, n, l + 1, r + 1); // клетки l+1..r
// начальное состояние после клетки l: (d_l, d_{l-1}) = (v_l, -inf); ответ — d_r
return max(v[l] + M.a, NEG + M.c); // первая компонента строки (v_l, -inf) · M
}
};3:04:42 Условие. Дан массив. Сколькими способами его можно разбить на отрезки так, чтобы сумма на каждом отрезке была положительна? (По модулю — в записи не названо, в коде $998244353$.) Лектор отмечает, что такая задача была на первом отборочном этапе и решили её очень немногие.
3:06:09 Решение. (1) Переходим к префиксным суммам $P_0=0,\ P_i=a_1+\dots+a_i$. Отрезок $(j,i]$ имеет положительную сумму ⇔ $P_j<P_i$. (2) Динамика: $dp_0=1$, $dp_i=\sum_{j<i,\ P_j<P_i}dp_j$ — число способов разбить префикс длины $i$ (последний отрезок $(j,i]$). Это $O(n^2)$ (3:14:52).
3:07:10 (3) Сжимаем координаты префиксных сумм: порядок сохраняется. (4) Строим дерево отрезков (или Фенвика), индексированное сжатым значением префиксной суммы. В ячейке с номером $k$ лежит сумма $dp_j$ по всем $j$ уже обработанным префиксам со значением $P_j$, сжатым в $k$. Тогда $dp_i$ — это сумма на префиксе по значениям строго меньше $P_i$; после вычисления $dp_i$ добавляем его в ячейку $P_i$. Итого $O(n\log n)$.
// Сколько способов разрезать массив на отрезки с положительной суммой (по модулю MOD)?
// dp[i] = Σ dp[j] по j < i с P[j] < P[i]; Фенвик по сжатым префиксным суммам P.
const long long MOD = 998244353;
long long countSplits(const vector<long long> &a) {
int n = a.size();
vector<long long> P(n + 1, 0);
for (int i = 0; i < n; i++) P[i + 1] = P[i] + a[i];
vector<long long> vals(P); // сжатие координат: порядок сохраняется
sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
vector<long long> bit(m + 1, 0);
auto add = [&](int i, long long x) { for (i++; i <= m; i += i & -i) bit[i] = (bit[i] + x) % MOD; };
auto pref = [&](int i) { long long r = 0; for (; i > 0; i -= i & -i) r = (r + bit[i]) % MOD; return r; }; // сумма по индексам < i
auto id = [&](long long p) { return int(lower_bound(vals.begin(), vals.end(), p) - vals.begin()); };
add(id(P[0]), 1); // dp[0] = 1: пустой префикс
long long dp = 1;
for (int i = 1; i <= n; i++) {
dp = pref(id(P[i])); // все j с P[j] < P[i]
add(id(P[i]), dp);
}
return dp; // dp[n]
}3:21:33 Разминочная версия предыдущей идеи. Сожмём значения до $0..m-1$ и построим дерево на максимум, индексированное значениями: в ячейке $x$ лежит длина наибольшей возрастающей подпоследовательности, заканчивающейся значением $x$. Читаем массив слева направо; для элемента $x$ ответ $=\max$ на префиксе значений $[0,x)$ плюс один; записываем его в ячейку $x$ (на максимум с имеющимся). Для восстановления самой подпоследовательности хранят позицию максимума и идут назад (3:45:40).
// Максимум на префиксе: нижнее (итеративное) дерево отрезков, значения 0..m-1
struct MaxTree {
int sz; vector<int> t;
MaxTree(int m) { sz = 1; while (sz < m) sz <<= 1; t.assign(2 * sz, 0); }
void chmax(int i, int v) { for (i += sz, t[i] = max(t[i], v); i > 1; i >>= 1) t[i >> 1] = max(t[i], t[i ^ 1]); }
int query(int l, int r) { // максимум на [l, r)
int res = 0;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, t[l++]);
if (r & 1) res = max(res, t[--r]);
}
return res;
}
};
// Длина наибольшей строго возрастающей подпоследовательности, O(n log n)
int lis(vector<int> a) {
vector<int> s(a); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end());
for (int &x : a) x = lower_bound(s.begin(), s.end(), x) - s.begin(); // сжатие: числа в 0..m-1
MaxTree T(s.size());
int best = 0;
for (int x : a) {
int len = T.query(0, x) + 1; // лучшая цепочка из чисел < x, плюс сам x
T.chmax(x, len); // в ячейке x — длина лучшей цепочки, заканчивающейся на x
best = max(best, len);
}
return best;
}
// НОП двух перестановок: сопоставим элементу a[i] его позицию в b — общая подпоследовательность превращается в возрастающую
int lcsPermutations(const vector<int> &a, const vector<int> &b) {
int n = a.size(); vector<int> posB(n + 1), c(n);
for (int i = 0; i < n; i++) posB[b[i]] = i;
for (int i = 0; i < n; i++) c[i] = posB[a[i]];
return lis(c);
}3:26:31 Инверсия — пара $i<j$, $a_i>a_j$. Идём слева направо, в дереве (Фенвике), индексированном сжатыми значениями, храним количество уже встреченных чисел каждого значения. Для текущего элемента число инверсий, в которых он — правый, равно сумме на суффиксе значений больше него.
3:29:20 $k$-инверсии — цепочки $i_1<\dots<i_k$ с $a_{i_1}>\dots>a_{i_k}$. Заведём $k$ деревьев: в $j$-м лежит число убывающих цепочек длины $j$, заканчивающихся данным значением (первое — просто счётчик чисел). Для нового элемента $x$ идём по длинам от большей к меньшей: число цепочек длины $j$, заканчивающихся в $x$, равно сумме на суффиксе значений $>x$ в дереве $j-1$; добавляем её в дерево $j$ (для $j=k$ достаточно прибавить к ответу). Идти нужно от больших $j$ к меньшим, чтобы элемент $x$ не использовался в цепочке дважды. Время $O(nk\log n)$.
// Число k-инверсий: цепочек i1 < ... < ik с a[i1] > a[i2] > ... > a[ik]; O(n k log n)
long long countKInversions(vector<int> a, int k) {
int n = a.size();
vector<int> s(a); sort(s.begin(), s.end()); s.erase(unique(s.begin(), s.end()), s.end());
for (int &x : a) x = lower_bound(s.begin(), s.end(), x) - s.begin() + 1; // значения 1..m
int m = s.size();
vector<vector<long long>> bit(k + 1, vector<long long>(m + 1, 0)); // bit[j] — Фенвик «цепочки длины j по последнему элементу»
auto add = [&](int j, int i, long long x) { for (; i <= m; i += i & -i) bit[j][i] += x; };
auto sum = [&](int j, int i) { long long r = 0; for (; i > 0; i -= i & -i) r += bit[j][i]; return r; };
long long total = 0;
for (int x : a) {
for (int j = k; j >= 2; j--) { // от длинных цепочек к коротким, чтобы не использовать x дважды
long long cnt = sum(j - 1, m) - sum(j - 1, x); // цепочки длины j-1 с последним элементом > x
if (j == k) total += cnt; // для последней длины достаточно просто суммы
else add(j, x, cnt);
}
add(1, x, 1); // цепочка из одного элемента
}
return k == 1 ? n : total;
}3:38:24 Условие. Даны две перестановки; найти длину наибольшей общей подпоследовательности (за $O(n\log n)$, а не $O(n^2)$).
3:39:50 Идея. Заменим каждое число $a_i$ первой перестановки его позицией $c_i$ во второй. Возрастающая подпоследовательность массива $c$ — это набор индексов $i_1<i_2<\dots$ в первой перестановке, которым соответствуют возрастающие позиции во второй, то есть общая подпоследовательность двух перестановок, и наоборот. Значит, НОП равна длине НВП массива $c$. (В записи массив определён условием $b_{c_i}=a_i$ — это та же позиция числа $a_i$ в $b$.)
3:47:06 Собственный пример. $a=(3,1,2,4)$, $b=(1,3,4,2)$. Позиции в $b$: $1\to0$, $3\to1$, $4\to2$, $2\to3$, поэтому $c=(1,0,3,2)$. НВП массива $c$ имеет длину 2 (например, $0,3$); наибольшая общая подпоследовательность $a$ и $b$ тоже имеет длину 2 (например, $3,4$). На записи пример разбирался с путаницей в индексах, лектор поправился по ходу.
lcsPermutations) сверена с динамикой $O(n^2)$ на 3000 случайных парах перестановок длины до 12.3:50:01 Условие. Даны $n$ отрезков (все $2n$ концов различны). Для каждого отрезка найти, сколько других отрезков его пересекают, но не лежат внутри него и не содержат его.
3:51:03 Решение. Сжимаем координаты (получается $2n$ точек), каждой точке сопоставлен тип события — открытие или закрытие отрезка. Для отрезка $i$ есть два непересекающихся типа «хороших» отрезков: (A) $l_j<l_i<r_j<r_i$ — начались раньше и закончились внутри; (B) $l_i<l_j<r_i<r_j$ — начались внутри и закончились позже. Задача симметрична: достаточно научиться считать (A), а (B) получается тем же кодом на «зеркально отражённых» отрезках.
3:56:21 Считаем (A) заметающей прямой слева направо с деревом/Фенвиком, в котором для закрытых отрезков стоит единица в ячейке их левого конца. Когда встречаем левый конец $l_i$, запоминаем $c_1=$ число закрытых отрезков с левым концом левее $l_i$. Когда встречаем правый конец $r_i$, берём $c_2=$ то же число и вычитаем: $c_2-c_1$ — количество отрезков, закрывшихся внутри $(l_i,r_i)$ и начавшихся левее $l_i$. После этого ставим единицу в ячейку $l_i$. Лектор называет и альтернативу: прибавлять единицу на левом конце, вычитать на правом, и на правом конце запрашивать сумму по отрезку $(l_i,r_i)$.
// Для каждого отрезка [l_i, r_i] (все 2n концов различны) — число отрезков, пересекающих его, но не вложенных ни в него, ни его в них.
// Слагаемое A: отрезки j с l_j < l_i < r_j < r_i. Слагаемое B получим тем же кодом на зеркальных отрезках.
vector<int> crossLeft(const vector<pair<int,int>> &seg) {
int n = seg.size(), M = 2 * n + 1;
vector<int> evL(M, -1), evR(M, -1); // событие на координате: номер отрезка, у которого здесь левый/правый конец
for (int i = 0; i < n; i++) { evL[seg[i].first] = i; evR[seg[i].second] = i; }
vector<int> bit(M + 1, 0), a(n), atLeft(n);
auto add = [&](int i) { for (i++; i <= M; i += i & -i) bit[i]++; };
auto cnt = [&](int i) { int r = 0; for (; i > 0; i -= i & -i) r += bit[i]; return r; }; // закрытых с l < i
for (int x = 1; x < M; x++) {
if (evL[x] >= 0) atLeft[evL[x]] = cnt(seg[evL[x]].first); // закрытые к моменту l_i с левым концом левее l_i
if (evR[x] >= 0) {
int i = evR[x];
a[i] = cnt(seg[i].first) - atLeft[i]; // закрылись внутри (l_i, r_i), а начались левее l_i
add(seg[i].first); // отрезок i закрыт: ставим единицу в его левый конец
}
}
return a;
}
vector<int> crossing(vector<pair<int,int>> seg) {
int n = seg.size(), M = 2 * n + 1;
vector<int> A = crossLeft(seg);
for (auto &s : seg) s = {M - s.second, M - s.first}; // зеркало: теперь «начавшиеся внутри и закончившиеся правее» стали типом A
vector<int> B = crossLeft(seg);
for (int i = 0; i < n; i++) A[i] += B[i];
return A;
}4:01:51 Условие. На поле стоят ладьи; даны прямоугольники-запросы. Для каждого нужно ответить, правда ли, что каждая клетка прямоугольника «побита» какой-то ладьёй внутри этого же прямоугольника (клетка бита, если в её строке или столбце, в пределах прямоугольника, есть ладья).
4:03:41 Ключевое замечание. Такая «ключевая» задача: сама проверка для одного прямоугольника неочевидна. Утверждение: прямоугольник полностью побит ⇔ в каждой его строке есть ладья, или в каждом его столбце есть ладья.
4:06:28 Доказательство. (⇐) Если в каждой строке есть ладья, то каждая клетка бита ладьёй своей строки. Для столбцов аналогично. (⇒) Допустим, найдётся строка без ладьи и найдётся столбец без ладьи (внутри прямоугольника). Тогда клетка на их пересечении не бита ни по строке, ни по столбцу — противоречие. Значит, хотя бы одно из «все строки покрыты», «все столбцы покрыты» выполняется.
4:10:49 Решение. Проверяем «в каждой строке есть ладья» для всех запросов сразу: сортируем запросы по $x_2$ и ладьи по $x$ и идём заметающей прямой по $x$. В дереве на минимум, индексированном строками $y$, храним $x$ последней ладьи в этой строке (для ещё не встреченных — 0). Когда доходим до $x_2$ запроса, берём минимум по строкам $[y_1,y_2]$ и сравниваем с $x_1$: в каждой строке есть ладья в $[x_1,x_2]$ ⇔ минимум $\ge x_1$. Для столбцов меняем $x$ и $y$ местами и запускаем тот же код (4:12:57), ответ — «или» двух проверок.
// Ладьи: прямоугольник «полностью под боем» ⇔ в каждой строке есть ладья ИЛИ в каждом столбце есть ладья (внутри прямоугольника).
// Заметающая прямая по x; дерево на минимум по y хранит x последней ладьи в этой строке (0 — не было).
struct Q { int x1, y1, x2, y2; };
vector<bool> everyRowHasRook(int n, const vector<pair<int,int>> &rooks, const vector<Q> &qs) {
int sz = 1; while (sz < n + 1) sz <<= 1;
vector<int> t(2 * sz, 0); // t[y + sz] = x последней ладьи на строке y
auto setv = [&](int y, int x) { for (y += sz, t[y] = x; y > 1; y >>= 1) t[y >> 1] = min(t[y], t[y ^ 1]); };
auto getmin = [&](int l, int r) { int res = INT_MAX; for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) { if (l & 1) res = min(res, t[l++]); if (r & 1) res = min(res, t[--r]); } return res; };
vector<int> orderR(rooks.size()), orderQ(qs.size());
iota(orderR.begin(), orderR.end(), 0); iota(orderQ.begin(), orderQ.end(), 0);
sort(orderR.begin(), orderR.end(), [&](int a, int b) { return rooks[a].first < rooks[b].first; });
sort(orderQ.begin(), orderQ.end(), [&](int a, int b) { return qs[a].x2 < qs[b].x2; });
vector<bool> res(qs.size());
size_t p = 0;
for (int qi : orderQ) {
while (p < orderR.size() && rooks[orderR[p]].first <= qs[qi].x2) { setv(rooks[orderR[p]].second, rooks[orderR[p]].first); p++; }
res[qi] = getmin(qs[qi].y1, qs[qi].y2 + 1) >= qs[qi].x1; // у каждой строки последняя ладья не левее x1
}
return res;
}
vector<bool> rooksCovered(int n, vector<pair<int,int>> rooks, vector<Q> qs) {
vector<bool> a = everyRowHasRook(n, rooks, qs);
for (auto &r : rooks) swap(r.first, r.second); // то же самое для столбцов: меняем x и y местами
for (auto &q : qs) { swap(q.x1, q.y1); swap(q.x2, q.y2); }
vector<bool> b = everyRowHasRook(n, rooks, qs);
for (size_t i = 0; i < a.size(); i++) a[i] = a[i] || b[i];
return a;
}4:13:39 Условие. Даны $n$ прямоугольников и $m$ точек. Для каждого прямоугольника найти число точек внутри. Нужно $O((n+m)\log m)$.
4:13:59 Решение. Сжимаем координаты по $y$. Заметающая прямая по $x$: события «добавить точку в ячейку $y$» и два запроса на каждый прямоугольник — на левой границе ($x_1-1$) и на правой ($x_2$). Запрос — сумма по $y\in[y_1,y_2]$; вклад правого запроса берётся со знаком «+», левого — «−». При равных $x$ точки обрабатываются раньше запросов. Префиксные суммы по двумерной таблице не годятся: точек много, таблица не помещается.
// Для каждого прямоугольника — число точек внутри (включая границу). Офлайн: заметающая прямая по x + Фенвик по y.
struct Rect { int x1, y1, x2, y2; };
vector<long long> pointsInRects(vector<pair<int,int>> pts, const vector<Rect> &rs) {
vector<int> ys; for (auto &p : pts) ys.push_back(p.second);
sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end()); // сжатие по y
int m = ys.size();
vector<int> bit(m + 1, 0);
auto add = [&](int i) { for (i++; i <= m; i += i & -i) bit[i]++; };
auto pref = [&](int i) { int r = 0; for (; i > 0; i -= i & -i) r += bit[i]; return r; }; // число точек с индексом y < i
struct Ev { int x, type, id; }; // type 0: добавить точку, 1: запрос «до x1», 2: запрос «до x2»
vector<Ev> ev;
for (int i = 0; i < (int)pts.size(); i++) ev.push_back({pts[i].first, 0, i});
for (int i = 0; i < (int)rs.size(); i++) { ev.push_back({rs[i].x1 - 1, 1, i}); ev.push_back({rs[i].x2, 2, i}); }
sort(ev.begin(), ev.end(), [](const Ev &a, const Ev &b) { return make_pair(a.x, a.type) < make_pair(b.x, b.type); }); // при равных x точки раньше запросов
vector<long long> ans(rs.size(), 0);
for (auto &e : ev) {
if (e.type == 0) { add(lower_bound(ys.begin(), ys.end(), pts[e.id].second) - ys.begin()); continue; }
const Rect &r = rs[e.id];
int lo = lower_bound(ys.begin(), ys.end(), r.y1) - ys.begin();
int hi = upper_bound(ys.begin(), ys.end(), r.y2) - ys.begin();
long long c = pref(hi) - pref(lo); // точки с x <= текущего и y в [y1, y2]
ans[e.id] += (e.type == 2 ? c : -c); // запрос до x2 даём со знаком «+», до x1-1 — «−»
}
return ans;
}4:15:46 Условие. Для перестановки $p_1,\dots,p_n$ даны числа $s_i=\sum_{j<i,\ p_j<p_i}p_j$. Восстановить $p$.
4:17:33 Общий приём. В задачах на восстановление пробуют четыре варианта: восстанавливать с начала, с конца, по минимальному, по максимальному элементу.
Способ 1: по минимальному элементу. Позиции с $s_i=0$ — это те, у которых слева нет меньших, то есть минимумы префиксов; их значения убывают слева направо. Значит, последняя позиция с $s_i=0$ содержит наименьший из них, то есть единицу. Находим её спуском по дереву на минимум (если минимум в правом поддереве равен 0 — идём вправо, иначе влево), объявляем единицей, вычитаем 1 из всех $s$ правее неё (массовая операция — пока не умеем) и ставим в её ячейку $+\infty$, чтобы она больше не считалась нулём и не портила вычитания. Инвариант сохраняется: $s_i$ — сумма меньших слева среди оставшихся чисел.
4:20:20 Способ 2: с конца. Для последнего элемента $x$ значение $s_n$ — это сумма всех чисел меньше $x$: $s_n=\tfrac{(x-1)x}2$, то есть $x$ определяется как наименьшее число, у которого сумма всех меньших чисел равна $s_n$. Затем $x$ удаляется из множества, и для $p_{n-1}$ нужно найти $x'$ — наименьшее из оставшихся чисел, у которого сумма оставшихся меньших чисел равна $s_{n-1}$. Ту же операцию повторяем: дерево, индексированное числами $1..n$, где в ячейке $v$ стоит $v$ (если число ещё свободно) или 0 (если уже использовано); нужно найти наименьшее $v$ с префиксной суммой $>s_i$.
4:27:21 Реализуется спуском по дереву за $O(\log n)$ (в Фенвике — стандартным побитовым спуском). Итого $O(n\log n)$.
// Восстановление перестановки по s[i] = сумма элементов слева от i, меньших p[i]. Идём с конца, Фенвик на «ещё не использованных» числах.
vector<int> restorePermutation(const vector<long long> &s) {
int n = s.size(), LOG = 1; while ((1 << LOG) <= n) LOG++;
vector<long long> bit(n + 1, 0);
auto add = [&](int i, long long x) { for (; i <= n; i += i & -i) bit[i] += x; };
for (int v = 1; v <= n; v++) add(v, v); // сначала все числа 1..n свободны (вес = само число)
vector<int> p(n);
for (int i = n - 1; i >= 0; i--) {
// x — наименьшее свободное число, у которого сумма свободных чисел до него включительно больше s[i] (спуск по Фенвику)
int pos = 0; long long rest = s[i];
for (int b = LOG; b >= 0; b--) {
int np = pos + (1 << b);
if (np <= n && bit[np] <= rest) { pos = np; rest -= bit[np]; }
}
p[i] = pos + 1;
add(p[i], -p[i]); // число использовано
}
return p;
}4:28:43 Остаток семинара прошёл в формате лекции: две структуры, которые «чуть-чуть ломают» стандартное дерево отрезков.
4:29:47 Задача. Массив; запросы: сколько чисел меньше $x$ на отрезке $[l,r)$.
4:30:10 Идея. До сих пор в вершине хранилось $O(1)$ информации. Теперь в вершине лежит весь её отрезок, отсортированный. Листья — одиночные числа; вершина получается слиянием двух отсортированных детей (как в сортировке слиянием). Для массива $5\ 3\ 6\ 7\ 2\ 8\ 1$ на нижнем уровне числа как есть, выше — пары $(3,5)$, $(6,7)$, тройка $(1,2,8)$ и т.д., в корне — весь массив по возрастанию.
4:32:46 Память и время построения. На каждом из $\log n$ уровней записано ровно $n$ чисел, поэтому память $O(n\log n)$; слияния суммарно тоже занимают $O(n\log n)$. Код отличается от обычного дерева только тем, что long long заменяется на vector, а «плюс» — на merge. Вместо вектора можно хранить set (проще, но построение медленнее в $\log$ раз) или любую структуру, которую можно сливать.
4:35:11 Запрос. Запрос разбивается на $O(\log n)$ вершин, как в обычном дереве; в каждой — бинарный поиск числа $x$. Складываем результаты. Время $O(\log^2 n)$. Слитый массив строить нельзя — это линейное время. Лектор отмечает, что такую задачу можно решить и за $O(\log n)$ — этим занимается следующая структура (и офлайн-сканирование с Фенвиком: сортируем числа и запросы).
4:37:40 Количество различных на отрезке. Заменим $a_i$ на позицию предыдущего такого же числа $prev_i$ (или $-1$). Число различных на $[l,r)$ равно числу позиций $i\in[l,r)$ с $prev_i<l$ — в каждой группе одинаковых только самый левый элемент «указывает» за левую границу. Это запрос «количество чисел меньше $l$ на отрезке» к Merge Sort Tree, построенному по массиву $prev$. Итого $O(\log^2 n)$ на запрос.
// Merge Sort Tree: в вершине — отсортированный массив её отрезка. Память O(n log 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 (l + 1 == r) { t[v] = {a[l]}; return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m, 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 countLess(int v, int l, int r, int ql, int qr, int x) { // сколько чисел < x на [ql, qr): O(log² n)
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return lower_bound(t[v].begin(), t[v].end(), x) - t[v].begin(); // бинпоиск внутри вершины
int m = (l + r) / 2;
return countLess(2 * v, l, m, ql, qr, x) + countLess(2 * v + 1, m, r, ql, qr, x);
}
};
// Количество различных на [l, r): prev[i] — позиция предыдущего такого же (или -1); различных = #{i in [l,r): prev[i] < l}
int countDistinct(const MergeSortTree &T, int l, int r) { return const_cast<MergeSortTree&>(T).countLess(1, 0, T.n, l, r, l); }
vector<int> prevEqual(const vector<int> &a) {
map<int,int> last; vector<int> p(a.size());
for (int i = 0; i < (int)a.size(); i++) { auto it = last.find(a[i]); p[i] = it == last.end() ? -1 : it->second; last[a[i]] = i; }
return p;
}4:40:34 Идея. «Нишевая» структура: в стандартном дереве мы делим позиции отрезком пополам. Теперь делим значения: берём середину диапазона значений (в записи — медиану; тогда глубина всегда $\log n$), элементы не больше середины отправляем в левого ребёнка, остальные — в правого, сохраняя относительный порядок. Для массива $6\ 7\ 2\ 1\ 8\ 5\ 4\ 3$ получаем: влево $2\ 1\ 4\ 3$, вправо $6\ 7\ 8\ 5$ и далее вниз, пока в вершине не останется одно значение. По сравнению с Merge Sort Tree структура «перевёрнута»: там вверху лежал отсортированный массив, а внизу — исходный; здесь наоборот.
4:45:55 Как сохранить отрезок позиций. Для каждой вершины хранится маска — для каждого элемента вершины, ушёл ли он влево — и префиксные суммы по ней (сколько из первых $i$ элементов ушло влево; остальные — вправо). Тогда отрезок $[l,r)$ в вершине превращается в отрезок $[ll,lr)$ в левом ребёнке, где $ll$ и $lr$ — значения префиксных сумм в $l$ и $r$, а в правом — $[\,l-ll,\ r-lr)$.
4:48:23 Запрос «сколько чисел меньше $x$ на $[l,r)$». Спускаемся по дереву значений: если диапазон значений вершины целиком меньше $x$, берём весь текущий отрезок позиций (его длину); если не меньше — выходим; иначе идём в обоих детей, пересчитывая отрезок по маске. Бинарный поиск не нужен: время $O(\log n)$.
4:55:02 Разбиение диапазона значений. Лектор делит по медиане: тогда в детях поровну элементов и глубина ровно $\log n$, но диапазоны значений детей не равны по длине, поэтому «среднее арифметическое границ» неприменимо — границы нужно хранить в вершине явно. Проблема повторов (одинаковые значения по обе стороны медианы) решается заменой числа на пару «значение, индекс» или сжатием в различные значения; на перестановках можно делить диапазон значений пополам, как в обычном дереве. В коде ниже вариант с делением диапазона значений пополам: глубина — $\log$ от размера диапазона (после сжатия значений это $O(\log n)$), одинаковые значения целиком уходят в одну сторону и не мешают.
// Wavelet Tree: вершина отвечает за диапазон ЗНАЧЕНИЙ [lo, hi]; хранит, сколько из первых i элементов ушло влево (значение <= mid).
struct Wavelet {
struct Node { int lo, hi; vector<int> toLeft; int L = -1, R = -1; };
vector<Node> t;
Wavelet(const vector<int> &a, int lo, int hi) { build(a, lo, hi); }
int build(const vector<int> &a, int lo, int hi) {
int id = t.size(); t.push_back({lo, hi, {}});
if (lo == hi || a.empty()) return id;
int mid = (lo + hi) / 2;
vector<int> left, right, pref(1, 0);
for (int x : a) { (x <= mid ? left : right).push_back(x); pref.push_back(pref.back() + (x <= mid)); } // сохраняем относительный порядок
t[id].toLeft = pref;
int l = build(left, lo, mid), r = build(right, mid + 1, hi);
t[id].L = l; t[id].R = r;
return id;
}
// сколько чисел < x среди позиций [l, r) (в терминах исходного массива)
int countLess(int id, int l, int r, int x) {
if (l >= r) return 0;
Node &nd = t[id];
if (x <= nd.lo) return 0;
if (nd.hi < x) return r - l; // диапазон значений целиком меньше x: берём весь текущий отрезок
int mid = (nd.lo + nd.hi) / 2;
int ll = nd.toLeft[l], lr = nd.toLeft[r]; // отрезок в левом ребёнке: [ll, lr)
return countLess(nd.L, ll, lr, x) + countLess(nd.R, l - ll, r - lr, x);
}
// k-я по величине (k с 0) среди [l, r) — спуск по дереву
int kth(int id, int l, int r, int k) {
Node &nd = t[id];
if (nd.lo == nd.hi) return nd.lo;
int ll = nd.toLeft[l], lr = nd.toLeft[r], inLeft = lr - ll;
if (k < inLeft) return kth(nd.L, ll, lr, k);
return kth(nd.R, l - ll, r - lr, k - inLeft);
}
};4:57:09 Различные на отрезке за $\log$. Сведение то же, что для Merge Sort Tree: заменяем число позицией предыдущего такого же и считаем «меньше $l$» на Wavelet Tree. 4:58:12 Задача для самостоятельного решения: $k$-я порядковая статистика на отрезке — спуск по Wavelet Tree: если в левом ребёнке на отрезке не менее $k$ чисел, идём влево, иначе вправо с вычитанием (функция kth в коде выше).