0:00 Линейные алгоритмы — те, что работают за $O(n)$. На этом занятии разбираются префиксные суммы (одномерные и двумерные), разностный массив и метод двух указателей. Про $O$-нотацию подробно говорилось на прошлом занятии и в мини-курсе по C++.
0:30 Условие. Дан массив $a_1,\dots,a_n$ ($n\le10^5$) и $Q$ запросов; запрос — пара $(L,R)$, нужно вывести сумму $a_L+a_{L+1}+\dots+a_R$. Пример: $a=(1,3,2,-1,7,4,2)$; запрос $(2,4)$ даёт $3+2-1=4$, запрос $(3,6)$ даёт $2-1+7+4=12$.
5:00 Наивное решение. На каждый запрос просто пройти по отрезку. Сумму надо хранить в long long: сумма int-ов может не влезть в int. Длина отрезка $R-L+1\le n$, значит один запрос стоит $O(n)$; все запросы вместе — $O(n\cdot Q)$, плюс $O(n)$ на ввод, то есть $O(n+nQ)=O(nQ)$. Это слишком долго. Ускорение ввода-вывода тут не поможет: упираемся в сам алгоритм, а не во ввод.
13:00 Наблюдение. Разные запросы проходят по одним и тем же элементам в одном и том же порядке (отрезки $[2,4]$ и $[3,6]$ пересекаются). Эту работу можно сделать один раз заранее.
15:00 Заведём массив $P$: $P_0=0$, $P_i=P_{i-1}+a_i$. Тогда $P_i=a_1+\dots+a_i$ — сумма всех элементов до позиции $i$ включительно. Для примера: $P=(0,1,4,6,5,12,16,18)$. Массив читают с единицы (нулевой элемент не используется), потому что так удобнее — запросы тоже приходят в 1-нумерации.
int n; cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<long long> P(n + 1, 0); // P[0] = 0 — важно!
for (int i = 1; i <= n; i++) P[i] = P[i - 1] + a[i];22:00 Ответ на запрос. Сумма $[L,R]$ — это сумма от начала до $R$ минус сумма от начала до $L-1$:
25:00 Частая ошибка — вычитать $P_L$ вместо $P_{L-1}$: тогда выбрасывается и сам элемент $a_L$. Запросы приходят в 1-нумерации, $L\ne0$; при $L=1$ вычитается $P_0$, поэтому обязательно $P_0=0$ (иначе все ответы сдвинутся).
int q; cin >> q;
while (q--) {
int l, r; cin >> l >> r;
cout << P[r] - P[l - 1] << "\n"; // O(1) на запрос
}26:00 Сложность. Предподсчёт — $O(n)$, каждый запрос — $O(1)$, всего $O(n+Q)$ вместо $O(nQ)$.
30:00 Суффиксные суммы — то же самое, только с конца (отдельно их обычно не вводят).
32:00 Почему: чтобы «вычесть префикс», нужна операция, обратная данной. У сложения обратное — вычитание, у умножения — деление ($\ne0$), а у максимума обратной нет: зная, что $\max(a,b)=a$, нельзя восстановить $b$. Итак, для идеи префиксов нужна обратимость операции; ещё нужна ассоциативность с возможностью переставлять элементы (сумма и произведение зависят только от множества элементов, а не от порядка).
36:00 Деление «на отрезке» и вычитание не определены: результат зависит от порядка. Если очень нужна конструкция $a_L/a_{L+1}/\dots/a_R=a_L\cdot\frac1{a_{L+1}}\cdots\frac1{a_R}$, её можно свести к префиксным произведениям обратных чисел, но такие задачи почти не встречаются.
42:00 Условие. Дан массив $a_1,\dots,a_n$; найти непустой подотрезок с максимальной суммой. Если все $a_i\ge0$, ответ — весь массив. Интересен случай, когда есть отрицательные: для $a=(1,2,-5,3,4)$ ответ — отрезок $(3,4)$ с суммой 7, а весь массив даёт только 5.
46:00 Подотрезок задаётся парой $L\le R$, его сумма — $P_R-P_{L-1}$. Простой перебор всех пар — $O(n^2)$. Зафиксируем $R$; нужно выбрать лучшее $L\le R$:
50:00 Объяснение: $P_R$ — константа при фиксированном $R$, её можно вынести; максимум разности достигается при минимальном вычитаемом. Значит, нужно знать минимальный из уже просмотренных префиксов $P_0,\dots,P_{R-1}$.
1:00:00 Оптимизация. При переходе от $R-1$ к $R$ множество допустимых $L-1$ расширяется ровно одним элементом $P_{R-1}$. Поэтому достаточно хранить одну переменную $t=\min(P_0,\dots,P_{R-1})$ и обновлять её: $t=\min(t,P_{R-1})$; ответ — $\max(\text{ответ},\,P_R-t)$. Внутренний цикл исчезает, получаем $O(n)$.
1:01:30 Прогон на массиве $(1,-2,3,4)$: $P=(0,1,-1,2,6)$.
| $R$ | $t$ (минимум $P_0..P_{R-1}$) | $P_R-t$ | ответ |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 0 | −1 | 1 |
| 3 | −1 | 3 | 3 |
| 4 | −1 | 7 | 7 |
Ответ 7 — отрезок $3+4$. Значение $P_R-t$ — лучшая сумма среди отрезков, заканчивающихся ровно в $R$; общий ответ — максимум по всем $R$.
// P[0] = 0, P[i] — префиксные суммы. Пустой отрезок разрешён (ответ >= 0).
long long ans = 0, t = 0; // t = min(P[0..R-1])
for (int r = 1; r <= n; r++) {
t = min(t, P[r - 1]); // добавили новый допустимый P[L-1]
ans = max(ans, P[r] - t); // лучший отрезок, заканчивающийся в r
}ans = LLONG_MIN; тогда для массива из одних отрицательных ответом будет наибольший элемент. Лектор берёт $ans=0$, то есть пустой отрезок разрешён.1:10:00 Условие. Дана таблица $n\times m$ (нумерация с 1) и $Q$ запросов; запрос — прямоугольник, нужно найти сумму чисел внутри него. Наивно — $O(nmQ)$: проход по всему прямоугольнику на каждый запрос. Хотим предподсчёт за $O(nm)$ и ответ на запрос за $O(1)$.
1:14:00 Теперь префикс — прямоугольник от левого верхнего угла $(1,1)$ до $(i,j)$: $P_{i,j}$ — сумма всех $a_{x,y}$ при $x\le i$, $y\le j$. Формула получения (развёрнутое объяснение, ход вывода по принципу включений-исключений):
Слагаемые $P_{i-1,j}$ и $P_{i,j-1}$ оба содержат прямоугольник до $(i-1,j-1)$, поэтому он посчитан дважды и один раз вычитается. Предподсчёт — двойной цикл по $i=1..n$, $j=1..m$, то есть $O(nm)$.
1:20:00 Запрос задаёт прямоугольник строки $L..R$, столбцы $X..Y$ (порядок параметров в условии нужно аккуратно проверять: $LRXY$ или $XYLR$). Берём большой прямоугольник до $(R,Y)$ и отрезаем лишнее:
Два вычитаемых — полосы сверху и слева; угловой прямоугольник до $(L-1,X-1)$ попал в обе полосы и вычтен дважды, поэтому его прибавляем обратно. Ответ на запрос — $O(1)$.
vector<vector<long long>> P(n + 1, vector<long long>(m + 1, 0)); // нулевая строка и столбец
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
P[i][j] = a[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
// запрос: строки l..r, столбцы x..y
long long s = P[r][y] - P[l - 1][y] - P[r][x - 1] + P[l - 1][x - 1];1:23:00 А в большей размерности? Лектор отмечает, что у родителей такая задача даже в 5 измерениях. Правило: в каждом измерении берётся либо правая граница, либо «левая минус единица». Перебираются все комбинации; знак — плюс при чётном числе «левых минус единица» и минус при нечётном. Для одного измерения: $P_R-P_{L-1}$; для двух — четыре слагаемых выше; для трёх — восемь: $+P_{RRR}$, три слагаемых со знаком «−» (одна левая), три со знаком «+» (две левых) и $-P_{LLL}$. Это формула включений-исключений.
1:29:00 Пусть дан массив префиксных сумм $P=(0,1,3,2,4)$. Можно ли восстановить исходный массив? Да: $a_i=P_i-P_{i-1}$. Получается $a=(1,2,-1,2)$. Такое преобразование называется разностным массивом: $D_i=a_i-a_{i-1}$, $D_0$ не используем (или 0). Префиксные суммы и разностный массив — обратные операции: префиксные суммы от $D$ дают $a$, разностный массив от $P$ тоже даёт $a$.
vector<long long> D(n + 2, 0);
for (int i = 1; i <= n; i++) D[i] = a[i] - a[i - 1]; // a[0] = 0
// восстановление: a[i] = a[i-1] + D[i] (префиксные суммы от D)1:35:00 Условие. Дан массив $a$ и $Q$ запросов $(L,R,X)$: ко всем $a_i$, $L\le i\le R$, прибавить $X$. Вывести массив после всех запросов. Наивно — $O(n)$ на запрос, всего $O(nQ)$.
1:36:00 Посмотрим, как запрос меняет разностный массив. Пример (собственный, но того же вида, что на записи): $a=(1,2,-1,4,6)$, запрос $L=2,R=4,X=3$. Было $D=(1,1,-3,5,2)$; после запроса $a=(1,5,2,7,6)$, $D=(1,4,-3,5,-1)$. Изменились ровно два элемента: $D_2$ выросло на 3, а $D_5$ уменьшилось на 3.
1:38:00 Почему так. Разности внутри отрезка (между двумя соседними элементами, к которым прибавили одно и то же) не меняются. Меняется только разность на левой границе — $a_L-a_{L-1}$ (прибавили к $a_L$, но не к $a_{L-1}$) — и на правой: $a_{R+1}-a_R$ (прибавили к $a_R$, но не к $a_{R+1}$). Итак:
1:40:00 Алгоритм. (1) Считаем $a$. (2) Строим $D$. (3) Каждый запрос — две операции над $D$: $O(1)$. (4) В конце префиксными суммами от $D$ восстанавливаем $a$. Итого $O(n+Q)$. Массив $D$ нужно делать на единицу длиннее (до $n+1$), чтобы $D_{R+1}$ при $R=n$ было куда писать.
vector<long long> D(n + 2, 0);
for (int i = 1; i <= n; i++) D[i] = a[i] - a[i - 1];
while (q--) {
int l, r; long long x; cin >> l >> r >> x;
D[l] += x; // начало диапазона
D[r + 1] -= x; // сразу после конца диапазона
}
long long cur = 0;
for (int i = 1; i <= n; i++) { cur += D[i]; cout << cur << " "; } // префиксные суммы от D = итоговый a1:44:00 Двумерный разностный массив лектор не разбирает: тема слишком сложная для этого занятия.
1:48:00 После перерыва (час, 18:00–19:00) идёт вторая часть — метод двух указателей: две «стрелки» на элементы массива (или двух массивов), которые только двигаются вперёд; каждый шаг цикла сдвигает хотя бы одну, поэтому суммарно шагов не больше длины массива.
1:48:00 Условие. Даны отсортированные по возрастанию массивы $a_1..a_n$ и $b_1..b_m$ ($n,m\le3\cdot10^5$), все числа в каждом различны. Найти количество чисел, которые есть в обоих. Нужно $O(n+m)$. Пример: $a=(1,3,4,5,8,10)$, $b=(2,3,8,9,10)$ — ответ 3 (числа 3, 8, 10). Решение через set с find стоит $O(n\log n)$ — дольше.
1:51:30 Идея. Указатели $i$ на $a$ и $j$ на $b$, оба сначала в начале. Если $a_i=b_j$ — нашли общее число, увеличиваем ответ и сдвигаем оба указателя. Иначе сдвигаем тот, что указывает на меньшее число. Почему: если $a_i<b_j$, то $a_i$ уже не встретится в $b$ правее $b_j$ (там числа ещё больше), так что его можно пропустить; если сдвинуть указатель на большее число, разность лишь вырастет, и совпадение пропустится.
int i = 0, j = 0, ans = 0;
while (i < n && j < m) { // пока оба указателя в границах
if (a[i] == b[j]) { ans++; i++; j++; }
else if (a[i] < b[j]) i++; // двигаем указатель на меньшее
else j++;
}1:58:00 Сложность. Каждый шаг двигает хотя бы один указатель, указатели только растут и не превосходят $n$ и $m$; значит, шагов не больше $n+m$, каждый $O(1)$: итого $O(n+m)$. Выхода за границы нет — условие цикла $i<n,\ j<m$ проверяется до каждого обращения. Сортировать массивы не нужно — сортированность и различность даны по условию.
2:01:00 Если в массивах есть одинаковые числа, спрашивают количество пар $(i,j)$ с $a_i=b_j$. В примере у лектора выходит 8: тройки и восьмёрки дают по одной паре (всего 2), а три десятки из $a$ и две десятки из $b$ дают $3\cdot2=6$ пар.
2:03:00 Случай $a_i\ne b_j$ обрабатывается как раньше. При равенстве находим, сколько подряд идущих таких же значений в каждом массиве: $c_1$ в $a$ и $c_2$ в $b$ (двигая указатели, пока значение то же), и прибавляем $c_1\cdot c_2$ — каждый из $c_1$ равных элементов $a$ образует пару с каждым из $c_2$ равных элементов $b$.
long long ans = 0; int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] < b[j]) i++;
else if (a[i] > b[j]) j++;
else { // одинаковые значения
int v = a[i]; long long c1 = 0, c2 = 0;
while (i < n && a[i] == v) { i++; c1++; } // блок равных в a
while (j < m && b[j] == v) { j++; c2++; } // блок равных в b
ans += c1 * c2; // все пары между блоками
}
}Ответ лучше хранить в long long: произведение $c_1c_2$ может быть большим.
2:10:00 Условие. Даны отсортированные $a$ (размера $n$) и $b$ (размера $m$). Нужно получить отсортированный массив $c$ размера $n+m$ из всех их элементов, за $O(n+m)$. Использование multiset не ускоряет: любая операция с ним стоит лишний множитель $\log$.
2:10:30 Заводим указатели $i,j$ и позицию записи $p$. Пока оба указателя в границах: меньший из $a_i$, $b_j$ записываем в $c_p$ и двигаем соответствующий указатель и $p$. Когда один из массивов закончился, нужно дописать остаток другого — иначе потеряем элементы: например, $a=(1,2,3)$, $b=(4,5,6)$ — $i$ дойдёт до конца, а $j$ останется нулём. Выполнится ровно один из двух хвостовых циклов. В конце $p=n+m$.
vector<int> c(n + m);
int i = 0, j = 0, p = 0;
while (i < n && j < m) {
if (a[i] < b[j]) c[p++] = a[i++];
else c[p++] = b[j++];
}
while (i < n) c[p++] = a[i++]; // остаток a
while (j < m) c[p++] = b[j++]; // остаток b2:18:00 Условие. Даны $n$ точек на прямой ($n\le3\cdot10^5$, $|x_i|\le10^9$) и число $k$. Найти количество пар $i<j$ с $|x_i-x_j|\le k$. Задача есть в контесте. Первый шаг — отсортировать (sort(x.begin(), x.end())) либо проверить, что массив уже отсортирован по условию. Пример: $x=(1,3,4,5,7,10)$, $k=2$: подходящие пары $(1,3)$, $(3,4)$, $(3,5)$, $(4,5)$, $(5,7)$ — ответ 5 (на записи сначала насчитали 4, потом пропущенную пару $(4,5)$ добавили — ответ 5).
2:24:00 Простое решение — два цикла: для каждого $i$ перебрать $j>i$ и проверять $x_j-x_i\le k$ (модуль не нужен — массив отсортирован); это $O(n^2)$. Оптимизация первая: как только $x_j-x_i>k$, делаем break — дальше правее точки ещё дальше.
2:25:30 Главное наблюдение: для фиксированного $i$ подходящие $j$ образуют отрезок $i+1..R_i$, где $R_i$ — самая правая подходящая точка (все точки между $i$ и $R_i$ лежат ближе, чем $R_i$, а правее $R_i$ — слишком далеко). Тогда $i$ даёт $R_i-i$ пар. Кроме того, $R_i$ не убывает с ростом $i$: при сдвиге $i$ вправо расстояние до $R_i$ не растёт. Значит, $R$ можно не искать заново, а двигать вправо, пока следующая точка ещё подходит:
sort(x.begin(), x.end());
long long ans = 0; int r = 0;
for (int i = 0; i < n; i++) {
r = max(r, i); // правая граница не может быть левее i
while (r + 1 < n && x[r + 1] - x[i] <= k) r++; // двигаем r вправо
ans += r - i; // пары (i, i+1), ..., (i, r)
}2:28:00 Сложность. Указатель $r$ только растёт и не выходит за $n$, указатель $i$ тоже: суммарно $O(n)$ (после сортировки, которая стоит $O(n\log n)$). Ответ хранить в long long — пар может быть порядка $n^2/2$.