0:00 Дан массив. Найти такие $i<j$, что $a_j - a_i$ как можно больше. Если массив отсортирован, достаточно взять первый и последний элементы, но он не отсортирован. Сделаем за линию.
1:21 Зафиксируем $j$. Чтобы разность была максимальной, нужен как можно меньший $a_i$ среди всех $i<j$. Идём по массиву слева направо и поддерживаем минимум уже просмотренных элементов; при сдвиге на один шаг этот минимум либо остаётся прежним, либо становится только что пройденным элементом.
int mn = a[0], ans = INT_MIN;
for (int j = 1; j < n; ++j) {
ans = max(ans, a[j] - mn); // лучшая пара с правым элементом j
mn = min(mn, a[j]); // теперь a[j] тоже «уже виден»
}6:07 Если нужны сами индексы, храним индекс текущего минимума и при улучшении ответа запоминаем пару (индекс минимума, $j$).
8:48 Теперь нужно найти $i,j$ с $j-i\ge k$, чтобы $a_i+a_j$ было максимальным. Снова фиксируем $j$ и хотим максимальный $a_i$ среди $i\le j-k$. Цикл запускаем с $j=k$, а в максимум на каждом шаге добавляем элемент $a_{j-k}$ — так расстояние гарантированно не меньше $k$:
int m = INT_MIN, ans = INT_MIN;
for (int j = k; j < n; ++j) {
m = max(m, a[j - k]); // максимум среди a[0..j-k]
ans = max(ans, a[j] + m);
}m элементом $a_{j-k}$, потом считаем ответ; иначе при $j=k$ в максимуме ещё ничего нет.x = max(x, y) на лекции для краткости называлась «макс равно» (x max= y — это мысленное обозначение, в C++ такого оператора нет).18:24 Дан массив и операция (пока что сложение). Нужно быстро отвечать на запросы «сумма на $[l,r)$». Наивный подход — считать сумму циклом: предпосчёт $O(1)$ (его нет вовсе), но каждый запрос $O(n)$; при большом числе запросов это плохо. Поэтому потратим время на предпосчёт, чтобы запросы были быстрыми.
19:50 Определим pref[0] = 0, а pref[i] — сумма первых $i$ элементов, то есть $a_0+\dots+a_{i-1}$ (сумма на полуинтервале $[0,i)$). Тогда
vector<long long> pref(n + 1, 0); // pref[0] = 0
for (int i = 1; i <= n; ++i)
pref[i] = pref[i - 1] + a[i - 1];23:59 Сумма на $[l,r)$, т. е. $a_l+\dots+a_{r-1}$, равна $pref_r - pref_l$. Действительно, $pref_r$ содержит все элементы от $0$ до $r-1$, а $pref_l$ — все от $0$ до $l-1$; при вычитании «лишнее» сокращается.
pref на один элемент длиннее.29:34 Почему не $r-1$: в определении $pref_r$ уже не входит элемент с индексом $r$ (это сумма до $r$ не включительно), поэтому ещё раз вычитать единицу не нужно.
30:58 Вместо сложения можно взять другую операцию. Минимум так считать нельзя: если в начале массива очень маленький элемент, то все «префиксные минимумы» совпадут с ним и по ним нельзя восстановить минимум на произвольном отрезке.
32:18 Подходит xor (побитовое «исключающее или», сумма по модулю 2 в каждом бите). Его свойства: $x\oplus x=0$ и $x\oplus 0=x$, поэтому $pref_r\oplus pref_l$ сокращает общий префикс и оставляет xor ровно нужных элементов.
36:27 Примечание: свойства операций на лекции перечислялись по памяти и обсуждались вперемешку; формулировка выше — аккуратная версия, оформленная как «Важное дополнение».
43:59 Пусть дана матрица $a$ размера $n\times m$. Определим $pref_{i,j}$ как сумму на «префиксной подматрице» — по строкам $[0,i)$ и по столбцам $[0,j)$. Чтобы вычислить $pref_{i,j}$, возьмём $pref_{i-1,j}$ (на строку выше) и $pref_{i,j-1}$ (на столбец левее), но общий кусок $pref_{i-1,j-1}$ мы посчитали дважды — вычтем его один раз и добавим новый элемент:
vector<vector<long long>> pref(n + 1, vector<long long>(m + 1, 0)); // рамка из нулей
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
pref[i][j] = pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1] + a[i-1][j-1];62:18 Нулевая строка и нулевой столбец — «рамка из нулей» (аналог $pref_0=0$ в 1D); руками ничего больше проставлять не нужно.
48:57 Нужна сумма на прямоугольнике по строкам $[l_1,l_2)$ и столбцам $[r_1,r_2)$. Берём весь большой префикс $pref_{l_2,r_2}$ и вычитаем лишнее: верхнюю полосу $pref_{l_1,r_2}$ и левую полосу $pref_{l_2,r_1}$. Верхний левый угол $pref_{l_1,r_1}$ при этом вычли дважды — возвращаем его:
51:06 Формулу подгонять под нужные индексы (в частности, под запросы в 1-индексации) можно, подставляя нужные границы: идея — «вырезать» нужный прямоугольник, вычитая лишнее и добавляя то, что вычли дважды.
53:51 Для трёхмерного массива определение то же: $pref_{i,j,k}$ — сумма по параллелепипеду $[0,i)\times[0,j)\times[0,k)$. Принцип построения: сначала складываем три префикса, получившиеся сдвигом ровно по одной оси; затем вычитаем три префикса со сдвигом по двум осям (они пересеклись); наконец добавляем префикс со сдвигом по всем трём осям и новый элемент:
63:40 Для запроса на прямоугольном параллелепипеде $[i_1,i_2)\times[j_1,j_2)\times[k_1,k_2)$ перебираем все $2^3=8$ комбинаций «левая/правая граница» по каждой оси; знак слагаемого — $(-1)^{p}$, где $p$ — число левых границ в комбинации (ноль левых — «$+$»: $pref_{i_2,j_2,k_2}$; одна левая — «$-$»; две — «$+$»; три — «$-$»: $pref_{i_1,j_1,k_1}$). Именно так одномерная формула $pref_r-pref_l$ и двумерная связаны одним правилом: для $d$ измерений — $2^d$ слагаемых, знак по чётности числа левых границ.
// d = 3: sum на [i1,i2) x [j1,j2) x [k1,k2)
long long q = 0;
int I[2] = {i1, i2}, J[2] = {j1, j2}, K[2] = {k1, k2};
for (int x = 0; x < 2; ++x)
for (int y = 0; y < 2; ++y)
for (int z = 0; z < 2; ++z) {
int lefts = (1 - x) + (1 - y) + (1 - z); // x = 1 — правая граница
q += (lefts % 2 ? -1 : 1) * pref[I[x]][J[y]][K[z]];
}70:46 Дан массив (числа могут быть отрицательными), нужен подотрезок с максимальной суммой за $O(n)$. Сумма на подотрезке — это $pref_r-pref_l$. Построим массив $pref$ и найдём в нём пару элементов $pref_l,pref_r$ ($l<r$) с максимальной разностью $pref_r-pref_l$ — это в точности разминочная задача.
// pref[0..n]; ищем max pref[r] - pref[l], l < r
long long mn = pref[0], ans = LLONG_MIN;
for (int r = 1; r <= n; ++r) {
ans = max(ans, pref[r] - mn);
mn = min(mn, pref[r]);
}72:07 Массив изначально нулевой. Сначала приходят $Q_1$ запросов «прибавить $x$ ко всем элементам отрезка $[l,r]$», потом $Q_2$ запросов «найти сумму на полуинтервале». Нужно уложиться в $O(Q_1+Q_2+n)$. Важно: все запросы первого типа идут до запросов второго (если они чередуются, задача сложнее и решается другими структурами данных).
76:54 Идея: не применять каждое прибавление по отдельности. Для запроса «прибавить $x$ на $[l,r]$» делаем две операции за $O(1)$: d[l] += x и d[r+1] -= x. Затем префиксные суммы массива $d$ дают в точности итоговый массив $a$ (прибавка «включается» в позиции $l$ и «выключается» после $r$).
vector<long long> d(n + 1, 0);
for (each query (l, r, x)) { // отрезок [l, r], индексация с нуля
d[l] += x;
d[r + 1] -= x;
}
vector<long long> a(n);
long long s = 0;
for (int i = 0; i < n; ++i) { s += d[i]; a[i] = s; } // первые префиксные суммы d дают массив a
// вторые префиксные суммы — для ответов на запросы суммы:
vector<long long> pref(n + 1, 0);
for (int i = 0; i < n; ++i) pref[i + 1] = pref[i] + a[i];
// сумма на [l, r): pref[r] - pref[l]81:42 Первые префиксные суммы восстанавливают массив $a$ (это не «префиксные суммы массива $a$», а сам $a$), поэтому для запросов суммы строим префиксные суммы ещё раз. Такой приём называется «оффлайн-прибавление на отрезке», а массив $d$ — разностным массивом: $d_i=a_i-a_{i-1}$. Он понадобится в задачах «прибавить на отрезке, узнать значение в точке».
83:44 Общая идея: заводим два указателя, каждый из которых двигается только вперёд, и по ходу поддерживаем нужную информацию. Суммарно каждый указатель делает не более $n$ шагов — решение линейное.
85:57 Сортировка слиянием делит массив пополам, сортирует половины и сливает их. Слияние (merge) двух отсортированных массивов $A$ (длины $n$) и $B$ (длины $m$) реализуется двумя указателями $i$ и $j$: сравниваем $A_i$ и $B_j$, меньший кладём в результат и двигаем соответствующий указатель; при равенстве берём из первого массива (он «раньше»).
vector<int> c;
int i = 0, j = 0;
while (i < n && j < m) {
if (a[i] <= b[j]) c.push_back(a[i++]);
else c.push_back(b[j++]);
}
while (i < n) c.push_back(a[i++]); // добить оставшийся хвост
while (j < m) c.push_back(b[j++]);88:48 Время $O(n+m)$: каждый указатель двигается только вперёд.
89:28 Заодно можно считать инверсии — пары $i<j$ с $a_i>a_j$. Когда мы кладём в результат $B_j$ (строго меньший, чем $A_i$), он образует инверсию со всеми ещё не взятыми элементами первого массива: $n-i$ штук (первый массив отсортирован). Знак «$\le$» при сравнении важен: равные элементы инверсию не образуют.
long long inv = 0;
// ... в ветке else (берём b[j]):
inv += n - i;92:18 Даны отсортированные массивы $A$ и $B$. Найти $i,j$, для которых $|A_i-B_j|$ минимально. Заводим два указателя; на каждом шаге пересчитываем ответ, затем двигаем указатель того, чей элемент меньше (если подвинуть больший, разность лишь увеличится).
int i = 0, j = 0, ans = INT_MAX;
while (i < n && j < m) {
ans = min(ans, abs(a[i] - b[j]));
if (a[i] < b[j]) i++;
else j++;
}97:27 Доводить оставшийся указатель до конца не нужно: если один массив закончился, то оставшиеся элементы другого только больше (и разность тоже), так что лучше ответ уже не станет.
103:00 Идея с бинарным поиском по префиксным суммам даёт $O(n\log n)$ (префиксные суммы возрастают, и для фиксированной правой границы можно найти нужную левую бинпоиском). Но можно за $O(n)$: фиксируем правую границу $r$ и двигаем левую $l$ вправо, пока сумма окна $[l,r]$ не меньше $k$. После цикла окно $[l,r]$ имеет сумму меньше $k$, но $[l-1,r]$ — не меньше, а значит, все левые границы $0,1,\dots,l-1$ дают подходящие подотрезки (при неотрицательных числах расширение влево только увеличивает сумму). К ответу прибавляем $l$.
long long ans = 0, sum = 0;
int l = 0;
for (int r = 0; r < n; ++r) {
sum += a[r]; // в начале итерации добавляем новый правый элемент
while (sum >= k) { // пока окно «слишком хорошее» — сжимаем слева
sum -= a[l];
l++;
}
ans += l; // левые границы 0..l-1 дают сумму >= k
}109:52 Прибавлять новый элемент надо в начале итерации (если мыслить отрезками); при работе с полуинтервалами — в конце. Время $O(n)$: за всё время $l$ делает не более $n$ шагов.
132:04 Фиксируем левую границу $l$ и двигаем правую $r$, пока сумма остаётся меньше $k$. Здесь удобно работать с полуинтервалами $[l,r)$: начальное состояние $r=0$, $sum=0$ — пустой полуинтервал. На лекции эта задача сначала решалась с включительными отрезками, а затем решение пришлось перерисовывать: при отсутствии ответа указатель $r$ может оказаться левее $l$ и всё ломается. С полуинтервалами достаточно проверки «пуст ли ответ».
int r = 0, ans = 0; // ans = 0 — подходящего подотрезка нет
long long sum = 0;
for (int l = 0; l < n; ++l) {
if (r < l) { r = l; sum = 0; } // окно пусто: a[l] >= k, начинаем заново
while (r < n && sum + a[r] < k) { // можно ли добавить a[r]?
sum += a[r];
r++;
}
ans = max(ans, r - l); // полуинтервал [l, r)
if (r > l) sum -= a[l]; // выкидываем a[l] из окна
}145:32 Опять фиксируем левую границу, двигаем правую пока сумма меньше $k$; как только сумма стала хотя бы $k$, проверяем, равна ли она $k$ в точности, и затем выкидываем левый элемент. Это то же самое, что «зафиксировать один указатель циклом, второй двигать вперёд»: так каждый шаг даёт гарантию, что другой указатель сдвинется на единицу, и нет сложных условий «кого двигать».
int r = 0, ans = INT_MAX;
long long sum = 0;
for (int l = 0; l < n; ++l) {
while (r < n && sum < k) sum += a[r++];
if (sum == k) ans = min(ans, r - l); // [l, r)
sum -= a[l];
}153:31 Заводим массив счётчиков cnt[1..K] и переменную uniq — число значений с ненулевым счётчиком. Добавляя $x$: если cnt[x]==0 перед увеличением — uniq++. Удаляя $x$: после уменьшения, если cnt[x]==0 — uniq--. Для правой границы $r$ двигаем левую вперёд, пока левый элемент встречается в окне более одного раза (его можно убрать без потери). Считаем, что все $a_i$ лежат в $[1,K]$; если в массиве бывают и другие значения, их надо пропускать (или завести cnt размером с максимум значений), иначе выйдем за границы массива.
vector<int> cnt(K + 1, 0);
int uniq = 0, l = 0, ans = INT_MAX;
for (int r = 0; r < n; ++r) {
if (cnt[a[r]]++ == 0) uniq++; // добавили a[r]
while (cnt[a[l]] > 1) { // a[l] есть ещё где-то в окне — удаляем
cnt[a[l]]--;
l++;
}
if (uniq == K) ans = min(ans, r - l + 1);
}156:19 Часть материала про стек с минимумом и очередь на двух стеках уже затрагивалась на прошлых лекциях (STL), поэтому здесь они даны кратко.
158:22 Нужно за $O(1)$ узнавать минимум среди всех элементов, лежащих в стеке. В стеке виден только верхний элемент, поэтому в каждом элементе храним пару: само значение и минимум всех элементов не выше него (то есть от дна до него включительно). При добавлении $x$ вторая компонента равна min(x, минимум предыдущей пары) (или просто $x$ для пустого стека). При удалении ничего пересчитывать не нужно: у лежащих ниже пар минимум относится только к ним.
vector<pair<int,int>> st; // (значение, минимум снизу вверх)
void push(int x) {
int mn = st.empty() ? x : min(x, st.back().second);
st.push_back({x, mn});
}
void pop() { st.pop_back(); }
int getMin() { return st.back().second; }162:25 Очереди нужен порядок «первым пришёл — первым ушёл», а у стека он обратный. Но если переложить все элементы из одного стека в другой, порядок развернётся — и получится нужный. Заводим два стека: в in кладём новые элементы, из out достаём. Если out пуст, а нужно извлечь элемент, полностью перекладываем in в out (порядок разворачивается) и достаём из out. Например, положили $4,7,2$ (в in сверху $2$), переложили — в out сверху $4$, затем $7$, затем $2$: порядок выхода $4,7,2$ — как и должен быть.
167:13 Каждая операция в среднем $O(1)$ — это амортизированная оценка: каждый элемент проходит за свою жизнь ровно три операции (добавление в in, перекладывание в out, удаление), поэтому $n$ элементов — не более $3n$ операций. Отдельная операция может быть долгой (перекладывание), но суммарно линейно.
165:51 Если оба стека сделать «с минимумом», то минимум во всей очереди — это минимум из минимумов in и out (то есть минимум верхних вторых компонент; пустой стек игнорируем).
// in, out — стеки пар (значение, минимум), как выше
void push(int x) { in.push_back({x, in.empty() ? x : min(x, in.back().second)}); }
int pop() {
if (out.empty())
while (!in.empty()) {
int x = in.back().first; in.pop_back();
out.push_back({x, out.empty() ? x : min(x, out.back().second)});
}
int x = out.back().first; out.pop_back();
return x;
}
int getMin() {
int m = INT_MAX;
if (!in.empty()) m = min(m, in.back().second);
if (!out.empty()) m = min(m, out.back().second);
return m;
}191:09 Стек с минимумом полезнее обычной очереди тем, что на стеке можно считать не только минимум, но и любую ассоциативную операцию (например, произведение матриц), а дек умеет только минимум.
169:18 Задача RMQ (range minimum query) — минимум на отрезке. Существуют сложные оптимальные решения за $O(n+q)$, но они нереалистичны на практике; классические — за $O(n\log n+q)$ или $O(n+q\log n)$ — будут позже. Частный случай, решаемый просто, — скользящее окно: и левые, и правые границы запросов упорядочены по возрастанию.
172:01 Тогда достаточно очереди с минимумом и двух указателей: сначала добавляем в очередь элементы до $R_1$, удаляем слева до $L_1$ — в очереди ровно отрезок $[L_1,R_1]$, получаем ответ; затем то же для $[L_2,R_2]$ и т. д. Для запросов, где один отрезок целиком внутри другого, метод не работает (после ответа на внутренний уже убран левый элемент внешнего, или наоборот).
175:27 Есть изящная реализация на деке. Хранить будем только кандидатов на минимум — индексы элементов окна, которые ещё когда-нибудь могут оказаться минимумом. Если в окне после элемента $x$ стоит элемент не больше него, то $x$ никогда не будет минимумом (любое окно, содержащее $x$, содержит и этот элемент, пока $x$ не удалён слева). Поэтому значения кандидатов, если смотреть слева направо, возрастают, а минимум окна — самый левый кандидат.
deque<int> dq; // индексы; значения a[dq[0]] < a[dq[1]] < ... (возрастают)
for (int i = 0; i < n; ++i) {
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back(); // эти кандидаты «мёртвые»
dq.push_back(i);
if (dq.front() <= i - w) dq.pop_front(); // вышел за окно длины w
if (i >= w - 1) cout << a[dq.front()] << " "; // минимум окна [i-w+1, i]
}189:43 Каждый элемент входит в дек и выходит из него не более одного раза — суммарно $O(n)$. В деке можно хранить и пары $(\text{индекс},\text{значение})$, это удобнее некоторым программистам.
195:54 Для каждого $a_i$ найти ближайший слева элемент, больший него: $left_i=\max\{j<i: a_j>a_i\}$. Для массива $5,3,1,4,2$: у $5$ такого нет, у $3$ — это $5$, у $1$ — $3$, у $4$ — $5$, у $2$ — $4$. Ближайший больший справа получается тем же кодом после разворота массива.
198:39 Идём слева направо и держим стек индексов кандидатов на роль «ближайшего большего слева» для будущих элементов. Приходит $a_i$: пока на вершине стека элемент не больше $a_i$, он больше никому не пригодится (правее и $a_i$, и он не больше) — выкидываем. Если стек не пуст, его вершина и есть $left_i$. Затем кладём $i$ в стек. Значения в стеке убывают снизу вверх.
vector<int> left(n), st; // st — индексы кандидатов (значения убывают)
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.back()] <= a[i]) st.pop_back();
left[i] = st.empty() ? -1 : st.back(); // -1 — «виртуальный элемент слева»
st.push_back(i);
}204:46 Каждый индекс попадает в стек один раз и один раз вылетает — суммарно $O(n)$. Это «локальные жадные шаги», которые не дают сделать лишних сравнений.
vector как стек можно, но обычно просто берут stack.213:01 Пусть для $a_i$ найдены $left_i$ и $right_i$ — ближайшие большие слева и справа; если их нет, берём $left_i=-1$, $right_i=n$ (виртуальные элементы бесконечной величины, это «лайфхак», при котором длины считаются правильно). Тогда $a_i$ — максимум на ровно $(i-left_i)\cdot(right_i-i)$ подотрезках: левую границу можно выбрать $i-left_i$ способами, правую — $right_i-i$.
215:06 Такой приём позволяет находить, например, подотрезок с максимальным значением «максимум умножить на сумму»: максимум для подотрезка известен, остаётся взять максимальную сумму в границах $(left_i,right_i)$.
223:12 Дан массив высот столбиков одинаковой ширины, стоящих рядом. Найти прямоугольник наибольшей площади, целиком лежащий под гистограммой (нижняя сторона — на оси).
225:56 Оптимальный прямоугольник можно считать касающимся «потолком» какого-то столбца (иначе его можно поднять «бесплатно»). Зафиксируем столбец $i$ высотой $h_i$: прямоугольник высоты $h_i$ растягивается влево и вправо, пока не упрётся в столбец ниже $h_i$. То есть нужны ближайшие меньшие слева и справа ($L_i$ и $R_i$ — их индексы, $-1$ и $n$ при отсутствии). Его ширина $R_i-L_i-1$, площадь $h_i\cdot(R_i-L_i-1)$.
228:48 Ближайшие меньшие слева и справа находятся тем же монотонным стеком (с условием «пока элемент на вершине не меньше текущего — выкидываем» и направлением вперёд / назад). Перебрав все столбцы, берём максимум площадей — это сведение задачи к предыдущей.
vector<int> L(n), R(n), st;
for (int i = 0; i < n; ++i) {
while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
L[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; --i) {
while (!st.empty() && h[st.back()] >= h[i]) st.pop_back();
R[i] = st.empty() ? n : st.back();
st.push_back(i);
}
long long ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, (long long)h[i] * (R[i] - L[i] - 1));236:18 Можно обойтись одним стеком, не сохраняя массивы $L,R$. Стек хранит возрастающую последовательность высот (индексы). Когда столбец $i$ выкидывает из стека элемент $t$ (потому что $h_t\ge h_i$), мы сразу знаем оба края: левый — следующий под ним в стеке (индекс или $-1$), правый — именно $i$. Считаем площадь $h_t\cdot(i-left-1)$. В конце добавляют «столбец высоты 0» в позиции $n$, чтобы вытолкнуть всё, что осталось в стеке.
long long ans = 0;
vector<int> st;
for (int i = 0; i <= n; ++i) {
int cur = (i == n) ? 0 : h[i]; // столбец высоты 0 в конце — вытолкнет всё
while (!st.empty() && h[st.back()] >= cur) {
long long t = h[st.back()]; st.pop_back();
int left = st.empty() ? -1 : st.back();
ans = max(ans, t * (i - left - 1));
}
st.push_back(i);
}237:46 Итог лекции: почти всё разобранное — «жадность на стеках»: стек с минимумом, очередь на двух стеках, монотонный стек, гистограмма. Очередь с минимумом на деке — альтернатива стековому варианту.