5:04 Запись начинается с настройки звука и разговоров до начала; содержательная часть стартует в 5:04. Лекция посвящена «необычным» вариантам дерева отрезков и родственным структурам: массовые операции, дерево Фенвика, дерево отрезков-сортировок (merge sort tree) с каскадированием, а затем серия задач на размерности — от одномерной до четырёхмерной. Основной лектор — первый преподаватель (в программе курса — Данис Валиуллин); ведущие занятия по ходу задают друг другу вопросы и спорят с залом, эти обсуждения передаются сжато.
5:36 Задача. На массиве нужны две операции: += x на отрезке и сумма на отрезке (5:25–5:51). Дерево отрезков с суммами строим как обычно: в каждой вершине хранится сумма на её отрезке, листья — элементы, корень — весь массив (5:56–6:57). Запрос суммы остаётся прежним; меняется только обновление (8:02–8:35).
8:41 Любой отрезок $[l,r]$ распадается на $O(\log n)$ полностью накрытых вершин. Если ко всем элементам вершины с $s$ листьями прибавить $x$, её сумма вырастет на $s\cdot x$ (9:49–10:39).
10:44 Почему нельзя просто обновить накрытые вершины и их предков. Тогда запрос по корню и по накрытым вершинам будет верным, но если спуститься ниже накрытой вершины, дети ничего не знают о прибавлении: информация о $x$ «потеряна» (10:44–12:50).
12:54 Ленивые операции. В каждой вершине храним два числа: сумму $\mathrm{sum}_v$ и отложенное прибавление $\mathrm{add}_v$ — сколько ещё нужно добавить сыновьям (12:54–13:44). Когда накрытая вершина получает $+x$, мы сразу правильно меняем её сумму ($+\,x\cdot\text{длина}$) и записываем $x$ в $\mathrm{add}$ обоих сыновей — а дальше «они уже сами разберутся» (13:19–14:07). Когда мы приходим в сына с ненулевым $\mathrm{add}$, ко всем листьям его поддерева нужно добавить $\mathrm{add}$, поэтому сумма растёт на $\mathrm{add}\cdot\text{длина}$, а сыновьям передаётся то же значение (14:07–15:11).
15:11 Это оформляется функцией push(v): прибавить $\mathrm{add}_v$ сыновьям, пересчитать сумму, обнулить $\mathrm{add}_v$ (15:11–15:46). Она ничего не портит: повторный вызов не изменит значений (15:46–16:15). Правило: вызывать push перед любым спуском вниз — и в запросе суммы, и в обновлении (16:15–16:52).
struct LazySum {
int n;
vector<ll> sum, add; // add[v] — сколько ещё нужно добавить сыновьям
LazySum(int n) : n(n), sum(4 * n, 0), add(4 * n, 0) {}
void apply(int v, int l, int r, ll x) { sum[v] += x * (r - l); add[v] += x; }
void push(int v, int l, int r) { // безвредно вызывать сколько угодно раз
if (!add[v]) return;
int m = (l + r) / 2;
apply(2 * v, l, m, add[v]); apply(2 * v + 1, m, r, add[v]);
add[v] = 0;
}
void update(int v, int l, int r, int ql, int qr, ll x) { // [ql, qr) += x
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { apply(v, l, r, x); return; }
push(v, l, r);
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];
}
ll get(int v, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return sum[v];
push(v, l, r);
int m = (l + r) / 2;
return get(2 * v, l, m, ql, qr) + get(2 * v + 1, m, r, ql, qr);
}
void update(int l, int r, ll x) { update(1, 0, n, l, r, x); }
ll get(int l, int r) { return get(1, 0, n, l, r); }
};17:22 Задача. На плоскости $n$ прямоугольников со сторонами, параллельными осям (они могут пересекаться и быть вложены); найти площадь их объединения. Ограничения: координаты до $10^9$, $n\le 10^5$ (17:19–18:48). Зал отмечает, что задача известная («баян»).
19:05 Сжатие по $y$. Оставим только те значения $y$, которые встречаются среди границ прямоугольников. Промежутки между соседними значениями — «полоски», у каждой есть вес (её длина), и площадь считается как сумма весов покрытых полосок на ширину (19:05–20:18). Различных полосок не больше $2n$, поэтому по ним можно строить дерево отрезков с массовыми операциями (20:18–20:38).
20:30 Заметающая прямая. Выпишем события по $x$ в один массив: «прямоугольник открылся» ($+1$ на отрезке полосок) и «закрылся» ($-1$). При равных $x$ сначала открытия, затем закрытия (20:30–21:22). Значение в полоске — сколько прямоугольников её сейчас накрывают, оно никогда не уходит ниже нуля, потому что закрытие идёт после открытия (21:36–22:25).
22:25 Между двумя соседними значениями $x_1<x_2$ набор накрытых полосок не меняется, и вклад в площадь равен $(\text{суммарный вес полосок со значением}>0)\cdot(x_2-x_1)$ (22:25–23:36). Нужна структура с операциями «прибавить на отрезке» и «вес позиций, не равных нулю» (23:36–23:56). Так как все значения неотрицательны, ненулевые — это «все, кроме нулевых», а нулевые — это минимальные, если минимум равен нулю. Поэтому в вершине храним минимум и суммарный вес позиций, где он достигается (24:03–25:12). Пересчёт вершины: если у сыновей минимумы равны — веса складываем, иначе берём меньший минимум с его весом (24:40–24:57); прибавление на всей вершине сдвигает минимум и не меняет количества (24:57–25:08).
25:12 Покрытая длина $=\text{общая длина}-(\text{вес минимумов, если минимум}=0)$, добавляем её, умноженную на $x_2-x_1$, к площади (25:12–25:52).
struct MinCount {
int n;
vector<ll> mn, add;
vector<ll> cnt; // суммарный вес позиций, где достигается минимум
MinCount(const vector<ll>& w) : n(w.size()), mn(4 * w.size(), 0), add(4 * w.size(), 0), cnt(4 * w.size(), 0) { build(1, 0, n, w); }
void build(int v, int l, int r, const vector<ll>& w) {
if (r - l == 1) { cnt[v] = w[l]; return; }
int m = (l + r) / 2;
build(2 * v, l, m, w); build(2 * v + 1, m, r, w);
pull(v);
}
void pull(int v) {
mn[v] = min(mn[2 * v], mn[2 * v + 1]);
cnt[v] = (mn[2 * v] == mn[v] ? cnt[2 * v] : 0) + (mn[2 * v + 1] == mn[v] ? cnt[2 * v + 1] : 0);
}
void apply(int v, ll x) { mn[v] += x; add[v] += x; }
void push(int v) { if (add[v]) { apply(2 * v, add[v]); apply(2 * v + 1, add[v]); add[v] = 0; } }
void update(int v, int l, int r, int ql, int qr, ll x) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { apply(v, x); return; }
push(v);
int m = (l + r) / 2;
update(2 * v, l, m, ql, qr, x); update(2 * v + 1, m, r, ql, qr, x);
pull(v);
}
pair<ll, ll> query(int v, int l, int r, int ql, int qr) { // (минимум, вес минимумов)
if (qr <= l || r <= ql) return {LLONG_MAX, 0};
if (ql <= l && r <= qr) return {mn[v], cnt[v]};
push(v);
int m = (l + r) / 2;
auto a = query(2 * v, l, m, ql, qr), b = query(2 * v + 1, m, r, ql, qr);
if (a.first < b.first) return a;
if (b.first < a.first) return b;
return {a.first, a.second + b.second};
}
void update(int l, int r, ll x) { update(1, 0, n, l, r, x); }
pair<ll, ll> query(int l, int r) { return query(1, 0, n, l, r); }
};ll union_area(const vector<array<int, 4>>& rect) { // {x1, y1, x2, y2}, x1 < x2, y1 < y2
vector<int> ys;
for (auto& r : rect) { ys.push_back(r[1]); ys.push_back(r[3]); }
sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
int m = (int)ys.size() - 1; // полоса i = [ys[i], ys[i+1]) с весом длины
if (m <= 0) return 0;
vector<ll> w(m);
for (int i = 0; i < m; i++) w[i] = ys[i + 1] - ys[i];
ll total = ys.back() - ys[0];
MinCount tree(w);
vector<array<int, 4>> ev; // {x, -тип, l, r}: открытие (+1) идёт раньше закрытия
for (auto& r : rect) {
int l = lower_bound(ys.begin(), ys.end(), r[1]) - ys.begin();
int h = lower_bound(ys.begin(), ys.end(), r[3]) - ys.begin();
ev.push_back({r[0], -1, l, h}); ev.push_back({r[2], 1, l, h});
}
sort(ev.begin(), ev.end());
ll area = 0;
for (size_t i = 0; i < ev.size(); i++) {
if (i) {
auto [mn, c] = tree.query(0, m);
ll covered = total - (mn == 0 ? c : 0); // ненулевые = всё минус нули
area += covered * (ev[i][0] - ev[i - 1][0]);
}
tree.update(ev[i][2], ev[i][3], -ev[i][1]); // -(-1) = +1 при открытии, -1 при закрытии
}
return area;
}26:30 По ходу зал спорит о нерекурсивном («снизу») дереве отрезков: оно пишется быстрее, чем «сверху», а при должном желании на нём можно сделать и массовые операции, но это сложно (27:11–27:53). В лекции задачи решаются «сверху».
28:14 Неявное (динамическое) дерево отрезков. Нужно дерево на отрезке размера до $10^{18}$, при том что запросов всего порядка $10^5$ (28:14–28:40). У вершины левый и правый сыновья могут быть не созданы (индекс $-1$); значение в несозданной вершине считается значением «по умолчанию» (нули или арифметическая прогрессия — что-нибудь, что легко посчитать без хранения) (29:10–29:54). При обновлении, если нужного сына нет, создаём его и идём дальше; при запросе — аналогично или просто считаем, что там нули (29:54–30:26). Запрос затрагивает $\log C\approx 60$ вершин, всего создаётся порядка $60Q$ вершин — гораздо меньше $10^{18}$ (30:26–30:45).
struct DynTree {
struct Node { ll sum = 0; int l = -1, r = -1; };
vector<Node> t; ll N;
DynTree(ll N) : N(N) { t.emplace_back(); }
int child(int v, bool right) {
int c = right ? t[v].r : t[v].l;
if (c < 0) { c = t.size(); t.emplace_back(); (right ? t[v].r : t[v].l) = c; }
return c;
}
void add(ll pos, ll x) { // a[pos] += x, создаём только вершины на пути
int v = 0; ll lo = 0, hi = N;
t[v].sum += x;
while (hi - lo > 1) {
ll m = (lo + hi) / 2;
bool right = pos >= m;
v = child(v, right);
(right ? lo : hi) = m;
t[v].sum += x;
}
}
ll get(int v, ll lo, ll hi, ll l, ll r) { // сумма на [l, r)
if (v < 0 || r <= lo || hi <= l) return 0; // отсутствующая вершина — нули
if (l <= lo && hi <= r) return t[v].sum;
ll m = (lo + hi) / 2;
return get(t[v].l, lo, m, l, r) + get(t[v].r, m, hi, l, r);
}
ll get(ll l, ll r) { return get(0, 0, N, l, r); }
};32:40 Определение. В ячейке $i$ дерева Фенвика хранится сумма элементов исходного массива на промежутке от $i$ вниз, не включая $i-2^k$, где $2^k$ — младший единичный бит числа $i$: для $i=8$ это сумма до нуля, для $i=3$ — до двойки (32:46–33:11). Ограничение по сути одно: нужна обратимая операция (сумма подходит), потому что запрос на отрезке сводится к двум префиксам: $\mathrm{sum}(l,r)=\mathrm{pref}(r)-\mathrm{pref}(l-1)$ (33:44–34:09).
36:26 Код — две короткие функции: for (; i <= n; i += i & -i) t[i] += x и for (; i > 0; i -= i & -i) ans += t[i]. Формулу $i\,\&\,(-i)$ можно просто запомнить: она работает потому, что числа в компьютере хранятся в дополнительном коде, где $-1$ — все единицы (36:34–37:38).
38:05 Построение — заполнить нулями и сделать $n$ обновлений, то есть $O(n\log n)$. Лектор в споре настаивает, что это нормально (запросы асимптотически логарифмические, а на степенях двойки работают даже быстрее), хотя за $O(n)$ тоже можно (38:05–40:48). Дерево Фенвика быстрее и занимает вчетверо меньше памяти, чем «дерево отрезков на $4n$» (33:18–33:26).
struct Fenwick {
int n; vector<ll> t;
Fenwick(int n) : n(n), t(n + 1, 0) {}
void add(int i, ll x) { for (; i <= n; i += i & -i) t[i] += x; } // индексы с 1
ll pref(int i) { ll r = 0; for (; i > 0; i -= i & -i) r += t[i]; return r; }
int kth(ll k) { // минимальное i с pref(i) >= k
int pos = 0;
for (int pw = 1 << __lg(n); pw; pw >>= 1)
if (pos + pw <= n && t[pos + pw] < k) { pos += pw; k -= t[pos]; }
return pos + 1;
}
};41:38 Идея. В каждой вершине дерева хранить не сумму, а весь отсортированный набор элементов её отрезка: в корне — отсортированный массив, в сыновьях — отсортированные половины. Это ровно то, что строит сортировка слиянием: рекурсивные вызовы возвращают отсортированные массивы, которые мы сохраняем (41:46–42:56).
lower_bound и складываем: $O(\log^2 n)$ (43:34–44:22).vector, удалить и добавить элемент долго. Заменим векторы на ordered set из pb_ds — обычное множество, у которого есть операции «номер ключа» (order_of_key) и «ключ по номеру» (find_by_order); тогда обновление и запрос работают за $O(\log^2 n)$ (44:47–47:35). Лектор советует просто запомнить подключение (ext/pb_ds/assoc_container.hpp, tree_policy.hpp, пространство имён __gnu_pbds) и признаёт, что оно работает примерно в четыре раза дольше, чем собственное декартово дерево (46:30–47:17).typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// s.order_of_key(x) — сколько элементов меньше x
// *s.find_by_order(k) — k-й по порядку элемент (с 0)47:59 Теперь о том, что в зале, по признанию слушателей, не знает никто. Цель: убрать лишний логарифм из запроса «сколько чисел меньше $x$ на отрезке» в дереве отрезков-сортировок. Обновлений при этом нет — структура строится один раз (48:41–49:12). Лектор оговаривает, что на практике оно часто работает не быстрее обычного дерева сортировок: хотя асимптотика на $\log$ лучше, память в 4 раза больше, много кэш-промахов; но приводит замер на сабмитах: без каскадирования около 1,91 с, с каскадированием 1,37 с. Конечно, всё зависит от качества реализации (48:52–54:11).
49:45 Идея. Массив корня получен слиянием массивов двух сыновей (двигаем два указателя, берём меньшее). Сделаем в корне один бинпоиск и найдём позицию $p$ первого элемента, не меньшего $x$ (49:45–50:35). Утверждение: для этого же запроса позиция в каждом сыне определяется по $p$ без бинпоиска:
51:52 Значит, для каждой позиции $i$ массива вершины достаточно заранее посчитать за линию, сколько из первых $i$ элементов пришло из левого сына (в левом сыне это его позиция, в правом — $i$ минус это число) — «следующий пришедший из другого массива» (51:52–52:53). Тогда один бинпоиск в корне и дальше обычный спуск по дереву, в котором в каждой вершине позиция известна «с неба»: $O(\log n)$ на запрос вместо $O(\log^2 n)$ (52:53–53:16). Память — $O(n\log n)$ с большим множителем (лектор говорит про «четыре» (53:16–53:27)).
55:14 На вопрос из зала («а если сверху есть ещё элементы между») лектор отвечает: лишние элементы можно просто игнорировать — бинпоиск в корне указывает куда-то в «сжатый» массив; нужен лишь «следующий неравный», он считается предподсчётом (55:14–56:12).
struct MergeSortTree {
int n; vector<vector<int>> val, toL; // toL[v][i]: сколько из первых i элементов val[v] лежат в левом сыне
MergeSortTree(const vector<int>& a) : n(a.size()), val(4 * a.size()), toL(4 * a.size()) { build(1, 0, n, a); }
void build(int v, int l, int r, const vector<int>& a) {
if (r - l == 1) { val[v] = {a[l]}; return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m, r, a);
auto &L = val[2 * v], &R = val[2 * v + 1];
val[v].resize(r - l); toL[v].assign(r - l + 1, 0);
size_t i = 0, j = 0;
for (int k = 0; k < r - l; k++) {
bool left = j == R.size() || (i < L.size() && L[i] <= R[j]);
val[v][k] = left ? L[i++] : R[j++];
toL[v][k + 1] = toL[v][k] + left;
}
}
int cnt(int v, int l, int r, int ql, int qr, int p) { // p — сколько элементов вершины v меньше x
if (qr <= l || r <= ql || p == 0) return 0;
if (ql <= l && r <= qr) return p;
int m = (l + r) / 2;
return cnt(2 * v, l, m, ql, qr, toL[v][p]) + cnt(2 * v + 1, m, r, ql, qr, p - toL[v][p]);
}
int count_less(int ql, int qr, int x) { // на [ql, qr): один бинпоиск в корне, дальше O(1) на вершину
int p = lower_bound(val[1].begin(), val[1].end(), x) - val[1].begin();
return cnt(1, 0, n, ql, qr, p);
}
};toL[i] (сколько из первых $i$ элементов пришло слева); при равных значениях слияние берёт левый элемент первым. Запросы «сколько меньше $x$» сверены с перебором на 200 случайных массивах, включая поиск $k$-й статистики на отрезке и число различных (см. ниже).56:58 Многомерное дерево Фенвика — то же самое, но вложенное: Фенвик по первой координате, в каждой ячейке — Фенвик по второй и так далее; сумма на прямоугольнике — по формуле включений-исключений из префиксных сумм (в двумерном случае четыре слагаемых) (56:58–58:21). «Размерный» вариант с картой вместо массива даёт неявное дерево Фенвика (57:09–58:08). Лектор замечает, что в ответ на вопрос «сколько знают» зал «знает всё», и переходит к сложным задачам (58:23–58:31).
58:31 Задача. Для отрезка $[l,r]$ найти $k$-й по величине элемент (58:31–58:56). Идея из зала — перебирать ответ бинарным поиском по значению (59:03–59:11). Лектор: сожмём координаты (получится перестановка), построим дерево отрезков-сортировок. Бинарный поиск по ответу: при кандидате $x$ посчитаем, сколько чисел на $[l,r]$ меньше $x$; если их не меньше $k$ — ответ левее (1:00:09–1:00:56). Время $O(\log^2 n)$ (1:01:07–1:01:17); лектор замечает, что и с каскадированием получится $\log^2$, поскольку бинпоиск по ответу даёт ещё один логарифм. Если есть обновления — заменяем отсортированные векторы на динамическую структуру (1:01:28–1:01:55).
// k-я порядковая статистика на [l, r): бинпоиск по ответу, O(log^2)
int kth_on_range(MergeSortTree& t, int l, int r, int k) { // k с 1
auto& all = t.val[1];
int lo = 0, hi = (int)all.size() - 1;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (t.count_less(l, r, all[mid] + 1) >= k) hi = mid; else lo = mid + 1;
}
return all[lo];
}1:02:09 Задача. Массив $a_1,\dots,a_n$; запросы: *= x на отрезке и $\gcd$ на отрезке (1:02:09–1:02:44). Идея из зала: хранить разложение на простые. В каждой вершине храним для каждого простого степень, с которой оно входит в $\gcd$ отрезка; умножение на $x$ — прибавление к соответствующим степеням (с лениво откладываемым значением, как раньше), а $\gcd$ двух сыновей — минимум по каждому простому, потому что простые независимы (1:08:18–1:09:17).
1:06:26 Сколько простых? Если значения в запросах ограничены $A=10^3$, то различных простых около $168$ (лектор округляет до $200$). В вершине храним массив из $\le 200$ счётчиков, обновление и слияние стоят $O(200)$ на вершину, итого $O(200\cdot q\log n)$. Это много, и в зале спорят про память и константу; вывод обсуждения — для таких ограничений решение проходит (1:07:42–1:10:53). Для значений до $10^8$ разложения на простые хранить в каждой вершине нельзя, поэтому в разборе значения ограничены $10^3$ (1:03:11–1:05:19).
1:11:03 Задача. Массив и запросы: изменить $a_i=x$; сколько таких $i\in[L,R]$, что $x\le a_i\le y$ (1:11:03–1:12:09). Это две задачи «сколько не больше $z$»: считаем на $[L,R]$ количество $\le y$ и вычитаем количество $<x$ — вариант дерева отрезков-сортировок (1:12:17–1:12:34).
1:12:49 Задача. Даны $n$ троек $(a_i,b_i,c_i)$. Тройка $i$ бесполезна, если существует $j$ с $a_j>a_i$, $b_j>b_i$, $c_j>c_i$. Сколько троек остаётся (1:12:41–1:13:25)? Зал предлагает неявное трёхмерное дерево Фенвика (максимум на «суффиксе» — трёхмерном ортанте): это даёт $\log^3$ с большой константой, и лектор просит «быстрее, чем куб» (1:14:06–1:15:23).
1:15:23 Двумерный случай. Отсортируем по $a$ по убыванию и пройдём, поддерживая максимум $b$ среди уже просмотренных: тройка (пара) бесполезна, если этот максимум строго больше её $b$ (1:16:13–1:18:47). Лектор записывает: сортировка по первому параметру превращает его «во время».
1:18:53 Три измерения. После сортировки по $a$ у нас остаются пары $(b,c)$, идём по ним справа налево (в порядке, в котором нас могут убить) и складываем во вспомогательное дерево: индекс — $b$, значение — максимум $c$. Для очередной пары спрашиваем максимум $c$ на суффиксе по $b$ (тех, у кого $b$ больше): если он больше нашего $c$ — нас убивают (1:19:50–1:21:12). Нужно именно число убитых, а не число пар «убийца—жертва», поэтому достаточно максимума (1:21:26–1:21:52). Время $O(n\log n)$.
vector<char> dominated_3d(const vector<array<int, 3>>& p) {
int n = p.size();
vector<int> bs;
for (auto& x : p) bs.push_back(x[1]);
sort(bs.begin(), bs.end()); bs.erase(unique(bs.begin(), bs.end()), bs.end());
int m = bs.size();
FenwickMax f(m); // по «перевёрнутому» b хранит максимум c: суффикс по b
auto rb = [&](int b) { return m - (int)(lower_bound(bs.begin(), bs.end(), b) - bs.begin()); }; // 1..m, больше b — меньше номер
vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int x, int y) { return p[x][0] > p[y][0]; });
vector<char> dead(n, 0);
for (int i = 0; i < n;) {
int j = i;
while (j < n && p[ord[j]][0] == p[ord[i]][0]) j++;
for (int k = i; k < j; k++) { // сначала все запросы группы: равные a друг друга не убивают
int id = ord[k];
if (f.get(rb(p[id][1]) - 1) > p[id][2]) dead[id] = 1; // есть b' > b с c' > c (c хранится +1, 0 = пусто)
}
for (int k = i; k < j; k++) { int id = ord[k]; f.upd(rb(p[id][1]), p[id][2]); }
i = j;
}
return dead;
}1:21:56 Четыре измерения. Попытки обойтись «по очереди» сжатием по каждой из переменных не работают (1:22:37–1:23:34): «обработать сколько-то параметров по отдельности и потом добавить ещё один» нельзя, нужно искать позицию, у которой все четыре больше, сразу (1:23:49–1:24:07). Многомерные Фенвики дают $\log^{d}$ и «можно сколько угодно измерений», но лектор утверждает, что можно обойтись одномерными структурами и получить $O(n\log^2 n)$ (1:24:14–1:25:34).
1:28:14 Разделяй и властвуй (CDQ). Первый ход — отсортировать по $a$ (индексы нам не нужны) (1:28:24–1:28:40). Далее функция solve(l, r) получает подотрезок, отсортированный по $a$, а возвращает отметки «убит» для пар внутри него и массив, отсортированный по $b$ (1:34:49–1:37:16, 1:41:06–1:42:25):
1:40:40 Структура по $(c,d)$. Для запроса «существует ли $c'>c$ и $d'>d$» достаточно хранить «ступенчатый стек» из несравнимых по $(c,d)$ пар: $c_1<c_2<\dots$ и $d_1>d_2>\dots$ (1:44:07–1:44:49). Вставка пары $(C,D)$: lower_bound по $c$ находит первую запись с $c'\ge C$. Если у неё $d'\ge D$, то новая пара бесполезна — не добавляем. Иначе удаляем все предшествующие записи с $d'\le D$ (они теперь бесполезны) и вставляем $(C,D)$ (1:45:24–1:47:01). Запрос $(C,D)$: берём первую запись с $c'>C$; у неё $d'$ среди подходящих наибольшее, поэтому достаточно сравнить $d'>D$ (1:47:09–1:48:34). Лектор в споре замечает, что здесь вместо дерева отрезков годится set.
struct Dominance4D {
vector<array<int, 4>> P; vector<char> dead;
Dominance4D(vector<array<int, 4>> p) : P(move(p)), dead(P.size(), 0) { // a попарно различны
sort(P.begin(), P.end());
solve(0, P.size());
}
// возвращает индексы [l, r), отсортированные по b; дополнительно отмечает убитых «через границу» половин
vector<int> solve(int l, int r) {
if (r - l == 1) return {l};
int m = (l + r) / 2;
auto A = solve(l, m), B = solve(m, r); // у B значения a больше, чем у A
vector<int> mg; mg.reserve(r - l);
size_t i = 0, j = 0;
while (i < A.size() || j < B.size()) { // слияние по b; при равных b правая половина идёт раньше
if (j == B.size() || (i < A.size() && P[A[i]][1] < P[B[j]][1])) mg.push_back(A[i++]);
else mg.push_back(B[j++]);
}
map<int, int> front; // «ступенчатый стек»: c растёт, d убывает
for (int k = (int)mg.size() - 1; k >= 0; k--) { // по убыванию b
int id = mg[k], c = P[id][2], d = P[id][3];
if (id >= m) { // из правой половины — добавляем в структуру
auto it = front.lower_bound(c);
if (it != front.end() && it->second >= d) continue; // нас уже перекрывают
if (it != front.end() && it->first == c) it = front.erase(it);
while (it != front.begin() && prev(it)->second <= d) front.erase(prev(it));
front[c] = d;
} else { // из левой — спрашиваем: есть ли c' > c и d' > d
auto it = front.upper_bound(c);
if (it != front.end() && it->second > d) dead[id] = 1;
}
}
return mg;
}
};1:49:37 Задача. Сколько различных чисел на отрезке $[l,r]$ (1:49:37–1:49:44)? Из зала: алгоритм Мо, оффлайн-вариант. Лектор показывает онлайн-решение на дереве отрезков-сортировок (1:49:44–1:50:31):
1:51:19 Зал спорит, что можно решить «корнячкой» (корневой декомпозицией); лектор отвечает, что с каскадированием получится быстрее, а вопрос реальной скорости зависит от константы (1:51:19–1:52:10).
// число различных на [l, r): считаем позиции, у которых следующее равное лежит за пределами отрезка
int distinct_on_range(MergeSortTree& tnext, int l, int r) { // tnext построено по nxt[i] = индекс следующего равного (или n)
return (r - l) - tnext.count_less(l, r, r);
}1:52:37 Условие. На поле падают яблоки; яблоко падает в момент $t$ в точке $x$. Есть ящики одинаковой длины $V$; каждый можно поставить в любую точку на время $D$ секунд подряд (один раз). Нужно собрать как можно больше яблок (1:52:37–1:53:58). Если смотреть на плоскость «время — координата», яблоки — точки, а ящики — одинаковые прямоугольники $V\times D$; нужно выбрать прямоугольники, покрывающие наибольшее число точек (1:55:07–1:55:27). Для одного ящика — максимальный подпрямоугольник (заметающей прямой с «+1 на отрезке» и максимумом), для двух возникают разбор случаев: прямоугольники не пересекаются (берём оптимальный для каждого) или пересекаются по какой-то общей точке (лектор предлагает перебирать самое левое и самое верхнее яблоко пересечения) (1:58:16–2:02:00). Простая идея «выбрать лучший, удалить яблоки, выбрать второй лучший» неверна: пример с тремя группами точек показывает, что жадность проигрывает сдвигу (2:03:54–2:04:49).
2:06:04 После лекции — перерыв (в записи он занимает несколько минут, 2:06:55–2:12:47). Затем преподаватель разбирает контест по теме «Математика 1» (часть задач разобрана в лекции, их повторять не будут, 2:13:08–2:13:20). В записи разбор идёт кратко, на идейном уровне.
2:13:20 Прямо считать НОД для каждой пары слишком долго, поэтому для каждого числа $d$ считаем количество пар, у которых НОД равен $d$ (2:13:23–2:13:40). Сначала берём все пары чисел, кратных $d$; затем вычитаем пары, у которых НОД кратен $d$, но строго больше $d$ — их мы уже посчитали для больших $d$ (2:13:40–2:13:50). Перебор всех $d$ вместе с их кратными работает за $O(n\log n)$ (гармонический ряд) (2:13:50–2:14:20).
2:14:28 Условие. Для подотрезка массива значение равно $\gcd$ на нём, умноженному на (сумма на нём минус максимум на нём). Нужно максимизировать значение по всем подотрезкам (2:14:28–2:15:12).
2:19:40 Итог лектор оценивает как $O(n\log A)$ на перебор значений $\gcd$ (2:19:40–2:19:56).
2:20:11 Даны количества вхождений каждой пары букв как соседних символов в строке из трёх букв $A$, $B$, $C$; нужно найти количество подходящих строк по модулю (2:20:13–2:20:51). Для двух букв это задача из лекции: известно число переходов между блоками $A$ и $B$, а буквы «шарами и перегородками» раскладываются по блокам (2:20:51–2:21:24).
2:21:24 Теперь добавляется буква $C$. Блоки из $C$ бывают трёх видов: вставленные внутрь группы $A$ (между двумя $A$), внутрь группы $B$ и между $A$ и $B$ (в любом из двух порядков). Блок $C$ между двумя $A$ вносит поровну в пары $AC$ и $CA$, между двумя $B$ — поровну в $BC$ и $CB$ (2:21:34–2:22:56). Лектор: перебираем количество блоков $C$ одного вида (в разборе — между $B$) (2:23:10–2:23:21). Остаток пар $BC$ и $CB$ определяет блоки на переходах $B\to A$ и $A\to B$, остаток $AC$ и $CA$ — блоки внутри групп $A$ (2:23:21–2:23:50). Для найденного количества блоков каждого вида остаётся перемножить числа способов «шарами и перегородками» (2:23:57–2:25:01). После предпосчёта факториалов и обратных к ним за $O(\text{длины строки})$ время работы линейное: перебор по количеству блоков и подсчёт по формулам из лекции (2:25:01–2:25:35).
2:26:05 Нужно посетить все достопримечательности, ходя по сетке; подсчитать число способов. Сведение, которое преподаватель уже рассказывала на прошлом занятии: вместо цикла из левого верхнего угла в правый нижний считаем пары непересекающихся путей — из клетки сразу за стартом в клетку сразу перед концом (2:26:51–2:27:10).
2:32:39 Переходы первого вида стоят $O(1)$ (всего $O(n^2)$), второго — $O(n)$, но таких состояний только $O(n)$, поэтому тоже $O(n^2)$ в сумме. Итог $O(n^2)$ плюс предпосчёт факториалов для числа путей между клетками (2:32:42–2:33:18).
3:17:00 После перерыва (2:34:20–3:17:00) — семинар. В начале ведущие проверяют новую трансляцию звука без входа в конференцию с компьютера, а затем семинар ведёт другой преподаватель: задачи идут «от простого к сложному», по ходу обсуждение с залом (3:17:00–3:18:36).
3:18:48 Когда пишут дерево отрезков «сверху», обычно выделяют массив на $4n$. На самом деле вершин не больше $2n$: на нижнем слое $n$ вершин, выше $n/2$, $n/4$ и так далее (3:19:16–3:19:55). Хочется индексацию, в которой нет пропусков (3:20:02–3:20:10). Стандартная нумерация — в порядке обхода в ширину (корень $0$, дальше $1,2,3,\dots$) оставляет «дыры», если дерево неполное (3:21:00–3:21:37).
3:21:37 Нумерация в порядке обхода в глубину. Пусть вершина получила номер $x$. Левому сыну даём $x+1$, а правому — $x+2\,(\text{размер левого отрезка})$: у левого поддерева на $s$ листьях ровно $2s-1$ вершин, так что правый сын идёт сразу за ним (3:21:48–3:22:37). Пропусков нет, и памяти нужно $2n$ вместо $4n$.
3:22:49 Есть и второй плюс: вершины лежат в памяти почти подряд, при спуске нет «странных прыжков» по памяти (3:22:49–3:23:13). Это особенно полезно, когда в вершине лежит что-то тяжёлое (строка, матрица переходов) — выигрыш по памяти и по кэшу примерно вдвое. Ведущий весь одиннадцатый класс писал так (3:23:13–3:23:34).
struct SegSum2n {
int n; vector<ll> t;
SegSum2n(const vector<ll>& a) : n(a.size()), t(2 * a.size()) { build(0, 0, n, a); }
void build(int x, int l, int r, const vector<ll>& a) { // отрезок [l, r)
if (r - l == 1) { t[x] = a[l]; return; }
int m = (l + r) / 2;
int L = x + 1, R = x + 2 * (m - l); // у левого поддерева 2(m-l)-1 вершин
build(L, l, m, a); build(R, m, r, a);
t[x] = t[L] + t[R];
}
ll get(int x, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return t[x];
int m = (l + r) / 2;
return get(x + 1, l, m, ql, qr) + get(x + 2 * (m - l), m, r, ql, qr);
}
ll get(int l, int r) { return get(0, 0, n, l, r); }
};3:23:45 Задача. Структура, которая умеет добавить число, удалить число и найти $k$-й по порядку элемент (3:23:45–3:24:28). Зал предлагает корневую, спуск по дереву отрезков, декартово дерево, ordered_set — ведущий отмечает, что последнее медленно и его нужно помнить (3:24:28–3:25:08).
3:25:08 Решение. Сожмём координаты (если запросы известны заранее) и заведём дерево отрезков (или Фенвика) по значениям: добавление числа $x$ — $+1$ в точке $x$, удаление — $-1$. $k$-й элемент — минимальный префикс с суммой не меньше $k$, находится спуском (3:25:16–3:26:26). Поскольку запросы только $+1$ и $-1$ в точке, достаточно дерева Фенвика (3:26:26–3:26:35).
Реализация спуска по Фенвику — метод kth в коде выше (раздел про Фенвика); он проверен в тесте против перебора. 3:29:12 Вывод ведущего: «чем писать декартач — фигня»; такой способ намного проще.
3:29:49 Задача. Операции: $+= x$ на отрезке и $\gcd$ на отрезке (числа до $10^9$ или около того, $n\le 5\cdot 10^4$) (3:29:49–3:30:15). Кажется, что $\gcd$ непредсказуемо меняется при прибавлении (то получает новые делители, то теряет), и надо подумать (3:30:23–3:30:46). Зал и чат ищут идею; ключ — свойство алгоритма Евклида (3:32:44–3:33:06):
3:33:14 Следствие: $\gcd(a_l,a_{l+1},\dots,a_r)=\gcd(a_l,\ a_{l+1}-a_l,\ \dots,\ a_r-a_{r-1})$ — достаточно знать $a_l$ и разности соседних (3:33:14–3:35:30). Прибавление $x$ на $[l,r]$ меняет только две разности: $d_l\mathrel{+}=x$ и $d_{r+1}\mathrel{-}=x$ (3:35:23–3:35:52). Значит:
Массовых операций (push) не нужно вовсе (3:35:30–3:35:59). Лектор уточняет, что догадаться до такого можно, если знать это свойство $\gcd$, а не «угадывая» сразу переход к разностям (3:35:59–3:36:08).
struct RangeAddGcd {
int n, sz; vector<ll> d, seg; Fenwick bit; // d[i] = a[i] - a[i-1]; bit хранит d, чтобы получить a[i]
RangeAddGcd(const vector<ll>& a) : n(a.size()), d(a.size()), bit(a.size() + 1) {
for (int i = 0; i < n; i++) { d[i] = a[i] - (i ? a[i - 1] : 0); bit.add(i + 1, d[i]); }
sz = 1; while (sz < n) sz <<= 1;
seg.assign(2 * sz, 0);
for (int i = 1; i < n; i++) seg[sz + i] = llabs(d[i]);
for (int v = sz - 1; v >= 1; v--) seg[v] = std::gcd(seg[2 * v], seg[2 * v + 1]);
}
void bump(int i, ll x) {
if (i >= n) return;
d[i] += x; bit.add(i + 1, x);
if (i == 0) return; // d[0] = a[0] в дереве НОД не участвует
int v = sz + i; seg[v] = llabs(d[i]);
for (v >>= 1; v; v >>= 1) seg[v] = std::gcd(seg[2 * v], seg[2 * v + 1]);
}
void add(int l, int r, ll x) { bump(l, x); bump(r + 1, -x); } // [l, r] += x
ll gcd_query(int l, int r) { // НОД на [l, r]
ll g = llabs(bit.pref(l + 1)); // a_l
ll res = 0;
for (int lo = l + 1 + sz, hi = r + 1 + sz; lo < hi; lo >>= 1, hi >>= 1) {
if (lo & 1) res = std::gcd(res, seg[lo++]);
if (hi & 1) res = std::gcd(res, seg[--hi]);
}
return std::gcd(g, res);
}
};3:36:17 Задача. Даны две перестановки; найти длину их наибольшей общей подпоследовательности быстрее, чем за квадрат (3:36:17–3:36:44). Для обычных массивов за квадрат умеем, но у перестановок все элементы различны.
3:36:52 Сведение к НВП. Для каждого числа из первой перестановки запоминаем его позицию. Идём по второй перестановке и заменяем каждое число на его позицию в первой; получается последовательность позиций. Общая подпоследовательность — это те числа, которые стоят в одном порядке в обеих перестановках, то есть возрастающая подпоследовательность в новой последовательности (3:37:07–3:42:25). Ответ — длина НВП (3:41:53–3:42:34).
3:42:34 НВП через Фенвика. Динамика: $d_p$ — длина лучшей возрастающей цепочки, оканчивающейся на значении $p$. При приходе нового значения $p$ берём максимум $d$ на префиксе $[0,p-1]$ и записываем в ячейку $p$ значение «максимум $+1$» (3:43:02–3:43:51). Требуются «максимум на префиксе» и «присвоить в точке», причём новые значения в ячейках только возрастают — этого достаточно, чтобы вместо суммы в дереве Фенвика хранить максимум (3:43:40–3:44:34). Если бы значение в ячейке могло уменьшиться, пересчитать накопленные максимумы было бы нельзя.
int lcs_of_permutations(const vector<int>& p, const vector<int>& q) { // значения 0..n-1
int n = p.size();
vector<int> pos(n);
for (int i = 0; i < n; i++) pos[p[i]] = i + 1;
FenwickMax f(n);
int best = 0;
for (int x : q) { // идём по q, для каждого числа берём его позицию в p
int len = f.get(pos[x] - 1) + 1; // длина лучшей цепочки, кончающейся левее в p
f.upd(pos[x], len);
best = max(best, len);
}
return best;
}3:44:50 Задача. $+= x$ на отрезке и сумма на отрезке — обычно решается деревом отрезков с push. Ведущий называет задачу «мозговзрывающей»: нужно обойтись деревом Фенвика (3:44:50–3:45:44). Если убрать любую из двух операций, задача легко решается разностным массивом; обе сразу — нет (3:45:44–3:46:02).
3:46:34 Пусть $d$ — разностный массив ($d_j=a_j-a_{j-1}$). Сумма на отрезке — разность двух префиксов (3:47:07–3:47:31). Сумма первых $r$ элементов:
3:47:36 Элемент $d_j$ войдёт в сумму столько раз, сколько $i$ лежат на $[j,r]$ (3:48:47–3:49:21). Получаем две суммы по префиксу: одна по $d_j$, другая по $j\,d_j$ — два дерева Фенвика (3:49:26–3:49:55). Прибавление $x$ на $[l,r]$ — две точечные правки разностного массива в обоих деревьях (3:49:55).
// S(r) = sum_{j<=r} d_j (r - j + 1) = (r + 1) * sum d_j - sum j * d_j
struct RangeFenwick {
Fenwick b1, b2;
RangeFenwick(int n) : b1(n + 1), b2(n + 1) {}
void upd(int i, ll x) { b1.add(i, x); b2.add(i, x * i); }
void add(int l, int r, ll x) { upd(l, x); upd(r + 1, -x); } // [l, r] += x, индексы с 1
ll pref(int r) { return (r + 1) * b1.pref(r) - b2.pref(r); }
ll get(int l, int r) { return pref(r) - pref(l - 1); }
};push 3:50:433:50:43 Ещё один способ решить ту же задачу. В массовых операциях обычно есть массив накопленных изменений (у нас — сколько нужно прибавить по поддереву), и функция push отправляет их вниз (3:50:52–3:51:57). Вызывать push на каждом шаге бывает дорого (в одной задаче с модулем и тяжёлой арифметикой это было причиной ТЛ) — можно не проталкивать изменения вниз (3:52:05–3:52:41, 3:56:34–3:57:09).
3:57:12 Отличие от обычного: с push изменение рано или поздно спускается вниз и «пропадает» из вершины, здесь оно остаётся в ней навсегда и учитывается каждый раз при пересчёте суммы предка и при запросе (3:57:18–3:58:38).
struct NoPushTree {
int n; vector<ll> sum, mod; // sum[v] учитывает все изменения внутри поддерева v; mod[v] — прибавка всем элементам v
NoPushTree(const vector<ll>& a) : n(a.size()), sum(4 * a.size(), 0), mod(4 * a.size(), 0) { build(1, 0, n, a); }
void build(int v, int l, int r, const vector<ll>& a) {
if (r - l == 1) { sum[v] = a[l]; return; }
int m = (l + r) / 2;
build(2 * v, l, m, a); build(2 * v + 1, m, r, a);
sum[v] = sum[2 * v] + sum[2 * v + 1];
}
void add(int v, int l, int r, int ql, int qr, ll x) {
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr) { mod[v] += x; sum[v] += x * (r - l); return; }
int m = (l + r) / 2;
add(2 * v, l, m, ql, qr, x); add(2 * v + 1, m, r, ql, qr, x);
sum[v] = sum[2 * v] + sum[2 * v + 1] + mod[v] * (r - l);
}
ll get(int v, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return 0;
if (ql <= l && r <= qr) return sum[v];
int m = (l + r) / 2;
ll res = mod[v] * (min(r, qr) - max(l, ql)); // вклад модификатора, который не спускали вниз
return res + get(2 * v, l, m, ql, qr) + get(2 * v + 1, m, r, ql, qr);
}
void add(int l, int r, ll x) { add(1, 0, n, l, r, x); }
ll get(int l, int r) { return get(1, 0, n, l, r); }
};4:00:18 Задача. Дан массив неотрицательных чисел и $Q$ запросов-отрезков $[L,R]$ (все запросы известны заранее). Ответ на запрос: сколько позиций $i\in[L,R]$ таких, что на суффиксе $a[i..R]$ минимальное неотрицательное число, которого там нет ($\operatorname{mex}$), равно максимуму на этом суффиксе плюс один (4:00:18–4:01:56, 4:24:44–4:25:29).
4:07:03 Переформулировка. Условие «$\operatorname{mex}=\max+1$» означает, что на суффиксе присутствуют все числа $0,1,\dots,\max$. Для неотрицательных чисел на суффиксе число различных значений всегда не больше $\max+1$ (возможные значения лежат в $[0,\max]$), а равенство достигается ровно когда присутствуют все (4:09:14–4:11:42, 4:15:41–4:16:35). Поэтому условие равносильно $\max+1-\text{distinct}=0$ — а величина $\max+1-\text{distinct}$ неотрицательна, и «нулей» среди неотрицательных чисел можно считать как минимум и количество минимумов — ровно структура из задачи про прямоугольники (4:13:09–4:16:52). Ответ на запрос: возьмём минимум и количество минимумов на $[L,R]$; если минимум равен нулю — ответ равен количеству, иначе нулю (4:16:35–4:17:04).
4:17:04 Заметаем $R$ слева направо. Поддерживаем массив $v_i=\max(a[i..R])+1-\text{distinct}(a[i..R])$ при шаге $R\to R+1$ и отвечаем на все запросы с этой правой границей (4:17:11–4:17:31). Новый элемент $x$ меняет две вещи:
4:23:46 Итого $O((n+Q)\log n)$. Ведущий для надёжности пересказывает идею второй раз (4:24:44–4:29:11).
// (то же самое: mex(a[i..R]) = max(a[i..R]) + 1). Оффлайн, заметаем R слева направо.
vector<int> count_full_suffixes(const vector<int>& a, const vector<pair<int, int>>& qs) { // запросы [L, R], с 0
int n = a.size();
MinCount tree(vector<ll>(n, 1)); // val[i] = max(a[i..R]) + 1 - (число различных в a[i..R])
vector<vector<pair<int, int>>> byR(n);
for (int i = 0; i < (int)qs.size(); i++) byR[qs[i].second].push_back({qs[i].first, i});
vector<int> ans(qs.size(), 0);
map<int, int> last; // последнее вхождение числа
vector<array<int, 3>> st; // стек суффиксных максимумов: {начало, конец, значение}
for (int R = 0; R < n; R++) {
int x = a[R];
auto it = last.find(x);
int prevPos = it == last.end() ? -1 : it->second;
last[x] = R;
tree.update(prevPos + 1, R + 1, -1); // +1 различное для всех левых границ правее прошлого вхождения
int start = R;
while (!st.empty() && st.back()[2] <= x) { // поглощаем блоки, где максимум был не больше x
auto [s, e, v] = st.back(); st.pop_back();
tree.update(s, e + 1, x - v); // старый максимум v заменяется на x
start = s;
}
tree.update(R, R + 1, x + 1); // новая позиция: максимум x и константа +1
st.push_back({start, R, x});
for (auto [L, id] : byR[R]) {
auto [mn, c] = tree.query(L, R + 1);
ans[id] = mn == 0 ? (int)c : 0;
}
}
return ans;
}4:29:21 Задача. Дан массив из $n$ чисел. Сколько существует способов разбить его на подряд идущие отрезки так, чтобы побитовое OR на отрезках строго возрастало (4:29:32–4:30:34)? Нужно быстрее, чем за квадрат (4:30:34–4:30:42).
4:31:03 Ключевой факт. Если зафиксировать правый конец $i$ и двигать левый, то значение OR только растёт, причём каждый раз, когда оно меняется, в нём включается новый бит; значит, различных значений OR на отрезках с общим правым концом не больше $\log A$. Поэтому пар «правый конец — значение OR» в сумме $O(n\log A)$, хотя всех отрезков $O(n^2)$ (4:32:46–4:34:57, 4:43:30–4:44:02).
4:35:13 Динамика «в лоб». $dp[i][x]$ — число разбиений префикса длины $i$, у которых последний отрезок имеет OR, равный $x$. Тогда $dp[i][x]=\sum_{j<i,\ \mathrm{OR}(j+1..i)=x}\ \sum_{y<x} dp[j][y]$ (4:35:20–4:37:38). Проблемы: $x$ принимает до $A$ значений (память $nA$), и есть «индикатор» $\mathrm{OR}(j+1..i)=x$ (4:37:52–4:39:15).
4:41:00 Геометрия. Нарисуем каждое состояние $(j,y)$ как точку на плоскости с весом $dp[j][y]$. Тогда $dp[i][x]$ — сумма весов в прямоугольнике $j\in[l_x,r_x]$, $y<x$ (4:41:34–4:43:23). Точек и запросов по $n\log A$ штук.
4:44:10 Заметающая прямая. Идём по $j$ слева направо; в дереве (по значению $y$) храним суммы уже добавленных точек. Прямоугольный запрос сумм — это разность двух префиксных по $j$: $F(r_x,x)-F(l_x-1,x)$, где $F(t,x)=\sum_{j\le t}\sum_{y<x}dp[j][y]$ (4:45:14–4:46:07). К моменту, когда мы доходим до $i$, значения $dp[i][\cdot]$ уже посчитаны: порог запроса строго меньше $i$ (4:46:07–4:46:55). Значения $y$ можно сжать до чисел $0,1,\dots$ — тогда дерево на $O(n\log A)$ ячеек (4:47:20–4:48:03); без сжатия — неявное дерево (4:47:09–4:47:20). Время $O(n\log A\log n)$. Ответ — сумма $dp[n][\cdot]$ (4:48:19–4:48:31).
int or_partitions(const vector<int>& a) {
int n = a.size();
struct Grp { int x, lo, hi; }; // OR(a[p..i]) = x для всех начал p в [lo, hi] (индексы с 1)
vector<vector<Grp>> g(n + 1);
vector<Grp> cur;
for (int i = 1; i <= n; i++) {
for (auto& e : cur) e.x |= a[i - 1];
cur.push_back({a[i - 1], i, i});
vector<Grp> nw; // склеиваем соседние группы с одинаковым OR; их не более log A
for (auto& e : cur) {
if (!nw.empty() && nw.back().x == e.x) nw.back().hi = e.hi; else nw.push_back(e);
}
cur = nw; g[i] = cur;
}
vector<int> xs = {-1}; // -1 — виртуальное «предыдущее значение» для первого отрезка
for (int i = 1; i <= n; i++) for (auto& e : g[i]) xs.push_back(e.x);
sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto id = [&](int x) { return int(lower_bound(xs.begin(), xs.end(), x) - xs.begin()) + 1; };
struct Qr { int i, k, sign; }; // для dp[i][g[i][k].x] нужно прибавить sign * F(t, x)
vector<vector<Qr>> at(n + 1); // at[t]: запросы с порогом t
vector<vector<ll>> dp(n + 1);
for (int i = 1; i <= n; i++) {
dp[i].assign(g[i].size(), 0);
for (int k = 0; k < (int)g[i].size(); k++) {
at[g[i][k].hi - 1].push_back({i, k, +1}); // j <= hi - 1
if (g[i][k].lo - 2 >= 0) at[g[i][k].lo - 2].push_back({i, k, -1}); // j <= lo - 2
}
}
Fenwick f(xs.size()); // по значению OR храним сумму dp[j][y]
for (int t = 0; t < n; t++) {
if (t == 0) f.add(id(-1), 1); // dp[0][-1] = 1
else for (int k = 0; k < (int)g[t].size(); k++) f.add(id(g[t][k].x), dp[t][k] % MOD);
for (auto& q : at[t]) {
ll v = f.pref(id(g[q.i][q.k].x) - 1) % MOD; // сумма по y < x
dp[q.i][q.k] = ((dp[q.i][q.k] + q.sign * v) % MOD + MOD) % MOD;
}
}
ll ans = 0;
for (ll v : dp[n]) ans = (ans + v) % MOD;
return ans;
}short и char всё равно занимает кратно двум байтам, а приведение указателей на невыровненный адрес — неопределённое поведение. Совет участнику с ТЛ и ML: заменить дерево отрезков на дерево Фенвика — по памяти это даёт около 20 раз (4:54:56–4:55:29).