Стек, очередь и дек — контейнеры C++ для хранения элементов, которые встречаются почти в каждой олимпиадной задаче. Они отличаются тем, откуда можно добавлять и откуда удалять элементы. Все основные операции у них работают за $O(1)$.
0:58 Стек (stack) — узкая длинная «коробочка», вроде вазы с теннисными мячиками: элементы кладут сверху, а достать можно только тот, что лежит сверху. Все остальные недоступны, пока не удалён верхний. Принцип: последним пришёл — первым вышел (LIFO). По сути это «урезанный вектор», в котором разрешено только добавлять в конец и удалять из конца. Обращаться по индексу нельзя.
1:48 Подключается как #include <stack>, объявляется stack<int> s; (в угловых скобках — тип элементов).
| Операция | Что делает | Время |
|---|---|---|
s.push(x) | кладёт x на вершину | $O(1)$ |
s.top() | возвращает значение на вершине, стек не меняется | $O(1)$ |
s.pop() | удаляет верхний элемент, ничего не возвращает | $O(1)$ |
s.size() | число элементов | $O(1)$ |
s.empty() | true, если стек пуст (то же, что s.size() == 0) | $O(1)$ |
stack<int> s;
s.push(10); s.push(20); s.push(30); // снизу вверх: 10, 20, 30
int t = s.top(); // t = 30, стек не изменился
s.pop(); // удалили 30; теперь вершина — 20
cout << s.size() << " " << s.empty(); // 2 0Чтобы узнать верхний элемент, его нужно сначала сохранить (int t = s.top();), а потом уже вызывать pop(): сам pop значение не отдаёт.
top() и pop() для пустого стека — неопределённое поведение (программа может упасть или выдать мусор). Перед обращением к вершине всегда проверяйте !s.empty(). Это же относится к front(), back(), pop() у очереди и дека.5:26 Очередь (queue) устроена так, как звучит: элемент, который пришёл первым, первым и уходит (FIFO). Если стек — вертикальная коробочка, то очередь — горизонтальная: новые элементы встают в конец, а удаляется элемент из начала.
6:46 Подключается #include <queue>, объявляется queue<int> q;.
| Операция | Что делает | Время |
|---|---|---|
q.push(x) | добавляет x в конец очереди | $O(1)$ |
q.front() | значение в начале (тот, кто уйдёт первым) | $O(1)$ |
q.back() | значение в конце (последний добавленный) | $O(1)$ |
q.pop() | удаляет элемент из начала, ничего не возвращает | $O(1)$ |
q.size(), q.empty() | размер и проверка на пустоту | $O(1)$ |
7:09 Пример: добавили $10$, $20$ — очередь $10, 20$; удалили $10$ — осталась $20$; добавили $30$ — очередь $20, 30$; удалили $20$ — осталась $30$. Доступа по индексу нет: q[2] писать нельзя.
9:49 Дек (deque, «двусторонняя очередь») — та же очередь, но добавлять и удалять можно с обоих концов. Подключается #include <deque>, объявляется deque<int> d;.
| Операция | Что делает | Время |
|---|---|---|
d.push_front(x), d.push_back(x) | добавить в начало / в конец | $O(1)$ |
d.pop_front(), d.pop_back() | удалить из начала / из конца | $O(1)$ |
d.front(), d.back() | первый и последний элементы | $O(1)$ |
d[i] | обращение по индексу — в деке оно разрешено | $O(1)$ |
d.begin(), d.end() | итераторы, как у вектора (например, для sort) | $O(1)$ |
d.resize(k) | изменить размер, как у вектора | $O(k)$ в худшем случае |
d.size(), d.empty() | размер и проверка на пустоту | $O(1)$ |
d.clear() | очищает весь дек (становится пустым) | $O(\text{размера})$ |
11:38 По возможностям дек — это полноценный вектор, к которому добавили быстрые вставку и удаление в начале. Методы front / back (12:17) — тот же «синтаксический сахар», что и top у стека, только можно посмотреть и на нижний элемент.
push_*, pop_*, front, back, size, empty и доступ по индексу у дека работают за $O(1)$ (добавления — амортизированно). Исключение — clear и resize: они стоят порядка числа удаляемых или создаваемых элементов, как и на лекции сказано про clear.swap 14:3014:30 Метод swap есть у всех этих контейнеров. Если есть два дека d и t, то d.swap(t) (или swap(d, t)) меняет их содержимое местами, и независимо от размеров это работает за $O(1)$: контейнеры просто обмениваются внутренними указателями, а сами элементы не копируются.
15:15 Вопрос слушателя. Ответ с лекции: стек, строго говоря, не нужен — вектор почти всегда не хуже, а дек даёт ещё больше возможностей. Основная польза от stack и queue — читаемость кода: тот, кто читает программу (в том числе вы сами через пару лет), сразу видит, что здесь используется только добавление и удаление с одного конца, и «рисует в голове» коробочку с мячиками.
push → v.push_back(x), top → v.back(), pop → v.pop_back(), empty → v.empty(). Скорость при этом не хуже. На лекции отдельно спросили, пройдёт ли такое решение на ревью, — точного ответа не прозвучало, преподаватель обещала уточнить. Для самой задачи ничего не меняется.16:49 Есть $n$ вертикальных столбиков, каждый шириной $1$, высоты $a_0, \dots, a_{n-1}$ (разные). Нужно найти прямоугольник наибольшей площади, целиком помещающийся под гистограммой, то есть прямоугольник, основание которого лежит на оси и покрывает подряд несколько столбиков, а высота не больше самого низкого из них. На лекции эту задачу назвали одной из самых важных для линейных алгоритмов.
17:58 В лоб: перебрать левую границу $l$ и правую границу $r$ и для каждой пары найти минимум высот на $[l,r]$. Площадь равна $(r-l+1)\cdot\min a_l..a_r$. Переборов границ $O(n^2)$, подсчёт минимума ещё $O(n)$ — итого $O(n^3)$, что слишком долго.
18:46 Будем перебирать столбик $i$ и считать, что он входит в ответ и является в нём самым низким — именно он определяет высоту прямоугольника. Такой прямоугольник можно растянуть влево и вправо, пока не встретится столбик ниже $a_i$. Поэтому нужны два числа для каждого $i$:
20:08 Чтобы не разбирать особые случаи, мысленно добавим «нулевые» столбики высоты $0$ с индексами $-1$ и $n$: если слева (справа) нет более низкого, ближайшим считается именно такой. Тогда $L_i=-1$ или $R_i=n$ означает «ничего не нашлось».
20:43 Высоту прямоугольника выше $a_i$ взять нельзя — рядом с $i$ он перестанет помещаться. Ниже брать нет смысла: между $L_i$ и $R_i$ все столбики не ниже $a_i$, поэтому можно «поднять» верх прямоугольника до $a_i$. Левая граница прямоугольника $l=L_i+1$ (следующий за ближайшим меньшим), правая $r=R_i-1$, ширина $R_i-L_i-1$:
$$S_i=(R_i-L_i-1)\cdot a_i,\qquad \text{ответ}=\max_i S_i.$$Задача свелась к поиску ближайшего меньшего слева и справа для каждого элемента. Искать справа можно так же, как слева — просто пройдя массив в обратную сторону (или перевернув его).
22:13 Идём по столбикам слева направо и поддерживаем стек индексов. Для очередного $i$:
22:32 Разберём на рисунке: пока поступают башенки $0$, $1$, $2$ с растущими высотами, каждая просто кладётся в стек. Когда приходит более низкая башенка, она снимает с вершины все столбики, которые выше или равны ей, и останавливается на первом более низком. Снятые столбики больше не пригодятся: для любой следующей башенки они хуже, чем текущая, — текущая и ниже, и правее них (а нужен ближайший меньший, то есть как можно правее). Потому их можно безвозвратно выбросить.
Интерактив: ползунок или ▶ — по шагам, как стек строит массив $L$ для высот 2, 1, 5, 6, 2, 3. Жёлтый — текущий столбик $i$, красный — снимаемый со стека, голубой — сейчас в стеке.
26:15 Почему тройка осталась в стеке и добавилась пятая башенка? Мы всегда кладём в стек текущую башенку. В примере с доски (там другие высоты) перед добавлением пятого элемента стек был $[0,3,4]$; четвёртый элемент выше пятого, поэтому снимаем его, а вершина «тройка» (индекс $3$) ниже — её мы и записываем как $L_5$, но не снимаем, потому что она может быть ближайшей и для следующих. После этого кладём индекс $5$.
28:22 Что такое «двигаем $R$»? Просто перебираем все столбики слева направо индексом $i$ и по очереди кладём каждый в стек, перед этим, возможно, сняв несколько предыдущих. Каждый индекс в конце концов оказывается в стеке.
29:43 Сначала функция принимает размер массива и сам массив (в лекции — f(n, a)), создаётся стек индексов и два массива из $n$ элементов: $L$ (изначально $-1$ — воображаемый нулевой столбик слева) и $R$ (изначально $n$ — воображаемый нулевой столбик справа).
stack<int> st; // храним индексы
vector<int> L(n, -1), R(n, n);
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop(); // вершина не ниже a[i] — убираем
if (!st.empty()) L[i] = st.top(); // ближайший меньший слева
st.push(i); // текущий столбик кладём всегда
}32:06 Порядок проверки в while важен: сначала !st.empty(), потом доступ к st.top(). В C++ условия && вычисляются слева направо и останавливаются на первой ложной части, так что к st.top() мы обращаемся только при непустом стеке.
36:19 Те же шаги по коду для высот $2,1,5,6,2,3$ (пошаговая проверка — в интерактиве выше); стек в начале пуст, $L=[-1,-1,-1,-1,-1,-1]$:
while, $L_0$ остаётся $-1$, кладём $0$.40:30 Если стек после цикла пуст, значит, ниже нашего столбика нет ничего на всём префиксе — все столбики слева были не ниже и сняты. Тогда в $L_i$ остаётся изначальное $-1$, то есть «нулевой» столбик воображаемой границы.
41:34 Ближайший меньший справа считается абсолютно так же, только индекс идёт в обратную сторону: $i$ от $n-1$ до $0$, а в $R_i$ кладётся вершина стека. Изначально $R_i=n$ (индекс воображаемого нулевого столбика в конце). Перед вторым проходом стек нужно очистить — после первого он, скорее всего, не пуст. Можно сделать st = stack<int>(); или завести новый стек.
42:26 Затем для каждого $i$ берём $l=L_i+1$, $r=R_i-1$, считаем $S=(r-l+1)\cdot a_i$ и обновляем ответ. Высота прямоугольника как раз $a_i$ — самый низкий столбик на $[l,r]$ (это пояснили студенту: любой столбик между $L_i$ и $R_i$ не ниже $a_i$, иначе бы он оказался ближе).
46:48 Итоговая функция целиком:
// Максимальная площадь прямоугольника в гистограмме; n — число столбиков, a[i] — высоты
long long f(int n, const vector<int>& a) {
stack<int> st; // в стеке — индексы столбиков
vector<int> L(n, -1), R(n, n); // L[i], R[i] — ближайшие строго меньшие слева/справа
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop(); // вершина не ниже a[i] — для i и дальше она бесполезна
if (!st.empty()) L[i] = st.top();
st.push(i);
}
st = stack<int>(); // перед вторым проходом стек надо очистить
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()] >= a[i])
st.pop();
if (!st.empty()) R[i] = st.top();
st.push(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
int l = L[i] + 1, r = R[i] - 1; // максимальный отрезок, где все столбики >= a[i]
long long s = (long long)(r - l + 1) * a[i];
ans = max(ans, s);
}
return ans;
}На примере $2,1,5,6,2,3$: $L=[-1,-1,1,2,1,4]$, $R=[1,6,4,4,6,6]$, площади $2,6,10,6,8,3$, ответ $10$.
int, но площадь — это ширина на высоту, и в реальной задаче она легко выходит за $2\cdot10^9$: нужен long long.clear или новый стек.while не больше $n$, а время работы — $O(n)$, хотя внутри цикла есть ещё один цикл. Это тот же амортизационный довод, что и для двух указателей. Память — $O(n)$.while56:20 Дана матрица $n\times m$ из нулей и единиц. Нужно найти прямоугольник максимальной площади, состоящий только из нулей. Задача очень похожа на гистограмму — это пример того, что гистограмма встречается часто и к ней многое сводится.
57:13 Зафиксируем нижнюю границу прямоугольника — строку $i$. Единицы в этой строке нас не интересуют: прямоугольник из нулей не может их содержать. А над каждым нулём лежит какое-то число нулей подряд до ближайшей единицы (выше уже неважно: единица ломает прямоугольник). То есть для каждого столбца $j$ имеем столбик из нулей высоты $h_j$, а прямоугольник, лежащий на строке $i$, — это прямоугольник под гистограммой высот $h_0,\dots,h_{m-1}$.
61:05 Для клетки $(i,j)$ высота $h[i][j]$ — длина столбика из нулей, который заканчивается в этой клетке. Считается небольшой динамикой от строки выше:
$$h[i][j]=\begin{cases}0,& a[i][j]=1,\\ h[i-1][j]+1,& a[i][j]=0.\end{cases}$$63:14 Строку $i=0$ в лекции считали отдельным циклом, чтобы не обращаться к несуществующей строке $-1$: там $h=0$ для единицы и $h=1$ для нуля. Затем для всех остальных строк пересчитывали по формуле. После подсчёта высот строки $i$ вызывается функция из предыдущей задачи f(m, h[i]) — она возвращает площадь наибольшего прямоугольника из нулей, лежащего нижней границей на строке $i$. Ответ — максимум по всем строкам.
// Матрица n×m из 0 и 1, ищем наибольший по площади прямоугольник из нулей
long long maxZeroRect(int n, int m, const vector<vector<int>>& a) {
vector<int> h(m, 0); // h[j] — высота столбика из нулей, который кончается в текущей строке
long long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
h[j] = (a[i][j] == 1) ? 0 : h[j] + 1;
ans = max(ans, f(m, h)); // гистограмма для строки i
}
return ans;
}h длины $m$, который обновляется на месте; для $i=0$ формула сама даёт верные значения ($h$ перед первой строкой равно $0$), так что отдельный цикл для нулевой строки не обязателен.f работает за $O(m)$ и вызывается $n$ раз; пересчёт $h$ — тоже $O(m)$ на строку. Итого $O(nm)$ — линейно по размеру входной матрицы, быстрее считать нельзя: матрицу надо хотя бы прочитать.push_back, back, pop_back, они делают то же самое. Но стек понятнее при чтении, а двумерный вектор — это просто «вектор векторов»: vector<vector<int>> h(n, vector<int>(m)).После перерыва — задачи контеста по теме «два указателя». В каждой разбирается идея, а не готовый текст.
75:02 Даны $n$, число $x$ и массив $a_i$. Нужно найти количество пар $i<j$ таких, что $a_j-a_i>x$ (в разборе — именно строго больше). Массив считаем отсортированным по неубыванию: на лекции он использовался именно так — и бинарный поиск, и два указателя применимы только к нему.
76:08 Способ 1: бинарный поиск. Перебираем правый конец $r$ и считаем, сколько левых концов подходит. Подходит каждый $l<r$ с $a_l<a_r-x$; так как массив отсортирован, это префикс. Его длину даёт lower_bound на префиксе до $r$ с ключом $a_r-x$ (число элементов строго меньше ключа). Ответ — сумма длин по всем $r$.
77:44 Способ 2: два указателя. Перебираем $r$ от $0$ до $n-1$ и двигаем левую границу: пока $a_l+x<a_r$, увеличиваем $l$. Для следующего $r$ значение $a_r$ только растёт, поэтому уже подходящий префикс остаётся подходящим, и левый указатель никогда не возвращается назад. Число подходящих левых концов для текущего $r$ равно $l$ (индексы $0..l-1$). Ответ — сумма всех $l$.
// A[0..n-1] отсортирован по неубыванию. Считаем пары i < j с a[j] - a[i] > x.
// Способ 1: бинарный поиск
long long pairsBinary(const vector<int>& a, int x) {
long long res = 0;
for (int r = 0; r < (int)a.size(); r++) {
// сколько элементов левее r строго меньше a[r] - x
res += lower_bound(a.begin(), a.begin() + r, a[r] - x) - a.begin();
}
return res;
}
// Способ 2: два указателя
long long pairsTwoPointers(const vector<int>& a, int x) {
long long res = 0;
int l = 0;
for (int r = 0; r < (int)a.size(); r++) {
while (l < r && a[l] + x < a[r]) l++; // l — число подходящих левых концов
res += l;
}
return res;
}79:36 Про смещения на единицу, которые обсуждали в зале: условие строгое, поэтому подходящие $a_l$ — это именно $a_l\le a_r-x-1$ (для целых), а все индексы строго левее найденной границы подходят. Из-за нумерации с нуля число таких элементов равно значению границы.
long long. Условие $l<r$ в while страхует от выхода за границы при отрицательных $x$ (при $x\ge0$ оно и так выполняется само).81:42 Даны $n_1,n_2,n_3,n_4$ — количества предметов (например, футболок и шорт) — и четыре массива $A,B,C,D$ соответствующих размеров. Нужно выбрать по одному элементу из каждого массива с индексами $i_1,i_2,i_3,i_4$ так, чтобы максимум из попарных разностей выбранных четырёх значений был минимален. Максимум попарных разностей — это то же самое, что $\max-\min$ четырёх чисел.
83:04 Решение: четыре указателя $l_1,l_2,l_3,l_4$ — по одному на массив (массивы отсортированы; если нет — отсортируйте). На каждом шаге:
84:42 На лекции пример показывали на рисунке с четырьмя массивами: берём минимальный из четырёх, сдвигаем, пересчитываем оценку. Закончить нужно, когда минимальный указатель сдвинуть уже нельзя — тогда лучше не станет. Это не то же, что «пока не кончатся все указатели»: когда один массив исчерпан, любые другие выборы уже содержат более поздние элементы остальных массивов, а значит, не лучше.
88:43 Пример с лекции: $A=\{1,3,5,7\}$, $B=\{4,6\}$, $C=\{11,12\}$, $D=\{2,4,6\}$. Начальная четвёрка $(1,4,11,2)$: оценка $11-1=10$. Минимум — в $A$, сдвигаем: $(3,4,11,2)$, оценка $9$. Минимум $2$ из $D$: $(3,4,11,4)$ — $8$. Минимум $3$: $(5,4,11,4)$ — $7$. Дальше $(5,6,11,4)$ — $7$, $(5,6,11,6)$ — $6$, $(7,6,11,6)$ — $5$. Теперь минимум $6$ в $B$, а $B$ закончился — стоп. Ответ $5$.
// Четыре отсортированных массива; выбираем по одному элементу, минимизируем max - min
int fourArrays(const vector<vector<int>>& v) {
int k = v.size();
vector<int> p(k, 0); // p[t] — указатель в массиве t
int best = INT_MAX;
while (true) {
int mn = INT_MAX, mx = INT_MIN, imn = 0;
for (int t = 0; t < k; t++) {
int x = v[t][p[t]];
if (x < mn) { mn = x; imn = t; }
mx = max(mx, x);
}
best = min(best, mx - mn); // оценка текущей четвёрки
if (++p[imn] == (int)v[imn].size()) break; // минимум двигать некуда — дальше лучше не станет
}
return best;
}92:48 Ещё во время разбора (86:50) слушательница предложила более «красивое» решение: сложить все элементы в один массив пар (значение, тип), где тип — номер массива (кепки — $0$, футболки — $1$ и т. д.), и отсортировать по значению. Теперь нужно найти кратчайший по значениям подотрезок, содержащий все четыре типа; его стоимость — разность значений на концах. Это обычные два указателя: правый добавляет элемент и увеличивает счётчик его типа; пока в окне есть все типы, обновляем ответ и сдвигаем левую границу.
// Тот же ответ другим способом: сливаем все элементы в один массив пар (значение, тип),
// сортируем и ищем самое короткое по значениям окно, содержащее все 4 типа
int fourWindow(const vector<vector<int>>& v) {
vector<pair<int,int>> all;
for (int t = 0; t < 4; t++)
for (int x : v[t]) all.push_back({x, t});
sort(all.begin(), all.end());
int cnt[4] = {0, 0, 0, 0}, kinds = 0, l = 0, best = INT_MAX;
for (int r = 0; r < (int)all.size(); r++) {
if (cnt[all[r].second]++ == 0) kinds++;
while (kinds == 4) { // окно [l, r] содержит все типы
best = min(best, all[r].first - all[l].first);
if (--cnt[all[l].second] == 0) kinds--;
l++;
}
}
return best;
}93:50 Это решение разобрали подробно. Все элементы с типами сливают в массив $A$ и сортируют; правую границу $r$ двигают от $1$ до $N$, а левую — пока на отрезке $[l,r]$ присутствуют все четыре типа (94:49 на лекции это сказано как «ровно четыре различных элемента»). Стоимость окна — $A_r.\text{first}-A_l.\text{first}$. Уточнение: окно сжимают, пока в нём есть все четыре типа, и каждый раз берут эту разность.
96:32 Преподаватель оценила идею как более запутанную для данной задачи («решение запарное»), но полезную в общем виде: она решает часто встречающуюся в олимпиадах задачу — найти кратчайший отрезок, содержащий все типы элементов. По этой схеме сделана и задача G ниже.
97:16 Как восстановить сами элементы: у найденного окна $[l,r]$ нужно взять из каждого типа любой элемент — в окне все типы есть, после этого можно пройтись по окну один раз и выбрать их.
100:28 Даны $n$ отрезков $[l_i,r_i]$. Нужно вывести их объединение — набор непересекающихся отрезков, покрывающих ту же часть прямой. Пересекающиеся отрезки сливаются в один, а между отрезками с зазором — раздельные. Например, на рисунке: первые два сливаются в один, следующие три тоже в один, последний остаётся отдельно.
101:52 Алгоритм:
// Объединение отрезков [l, r]; возвращает список непересекающихся отрезков
vector<pair<int,int>> unionSegments(vector<pair<int,int>> s) {
sort(s.begin(), s.end()); // по левой границе, при равенстве — по правой
vector<pair<int,int>> res;
int L = s[0].first, R = s[0].second; // текущий «собираемый» отрезок
for (size_t i = 1; i < s.size(); i++) {
if (s[i].first <= R) // пересекается с [L, R] — продлеваем вправо
R = max(R, s[i].second); // max: новый отрезок может целиком лежать внутри
else { // зазор — [L, R] готов
res.push_back({L, R});
L = s[i].first; R = s[i].second;
}
}
res.push_back({L, R});
return res;
}106:37 Что если новый отрезок целиком лежит внутри $[L,R]$? Тогда ничего менять не нужно: $R=\max(R,r)$ сохранит прежнее значение. Сравниваем всегда с текущим «большим» отрезком $[L,R]$, а не с предыдущим исходным.
108:19 Есть две последовательности: $a_i=i^2$ (то есть $0,1,4,9,\dots$) и $b_i=i^3$ ($0,1,8,27,\dots$). Нужно объединить их без повторов, отсортировать и вывести $X$-й по порядку элемент ($X$ до $10^7$).
108:48 «В лоб» не получится: сложить всё в один массив и отсортировать — это порядка $2X$ элементов (около $2\cdot10^7$) и сортировка за $O(X\log X)$, то есть порядка $5\cdot10^8$ операций; а за секунду C++ делает порядка $10^8$–$2\cdot10^8$ простых операций, так что это слишком долго.
111:04 Поэтому делаем два указателя, как при слиянии двух отсортированных массивов. Первый указатель стоит на очередном квадрате, второй — на очередном кубе. Смотрим на оба значения, берём меньшее как следующий элемент объединения и сдвигаем соответствующий указатель; если значения равны (как $0$ и $1$ в начале), берём одно и сдвигаем оба. Повторяем $X$ раз.
112:17 На примере: оба указателя на $0$ — берём $0$, сдвигаем оба; затем $1$ и $1$ — берём $1$, сдвигаем оба; теперь $4$ и $8$ — берём $4$ и сдвигаем первый; $9$ и $8$ — берём $8$ и сдвигаем второй, и т. д.
// X-й по порядку элемент объединения {i^2} и {i^3}, i = 0, 1, 2, ... (без повторов)
long long kthOfUnion(long long X) {
long long i = 0, j = 0, cur = 0; // указатели на квадрат i^2 и куб j^3
for (long long step = 0; step < X; step++) {
long long a = i * i, b = j * j * j;
if (a < b) { cur = a; i++; }
else if (b < a) { cur = b; j++; }
else { cur = a; i++; j++; } // равные числа берём один раз
}
return cur;
}long long: $X$-й элемент не больше $(X-1)^2\approx10^{14}$, поэтому второй указатель никогда не уходит далеко, и числа не переполняются. Первые элементы объединения: $0,1,4,8,9,16,25,27,36,49,\dots$.114:15 $N$ спортсменов бегут дистанцию длиной $L$ километров, у $i$-го на километр уходит $v_i$ минут. Они стартуют с интервалом в минуту: $i$-й — в момент $i$. Нужно найти число обгонов: пар, где один стартовал позже, но финишировал раньше.
115:46 Время финиша $i$-го спортсмена: $a_i=i+v_i\cdot L$ (момент старта плюс время в пути). Пара $i<j$ — обгон, если спортсмен $j$ стартовал позже, но финишировал раньше: $a_i>a_j$. То есть нужно посчитать число инверсий в массиве $a$ — пар $i<j$ с $a_i>a_j$.
117:29 Идея: сортировка слиянием. Делим массив пополам, рекурсивно сортируем обе половины. Теперь на слиянии надо учесть инверсии, где левый элемент — из левой половины, правый — из правой (инверсии внутри половин уже посчитаны рекурсивно). Обе половины отсортированы, поэтому для каждого элемента $a_r$ правой половины нужно число элементов левой, строго больших $a_r$. Двигаем $r$ по правой половине слева направо, а указатель $l$ по левой — вправо, пока $a_l\le a_r$. Когда $l$ остановился, все элементы левой половины с индексами от $l$ до конца — строго больше $a_r$, их число — $\text{размер}-l$. Сумму этих значений по всем $r$ прибавляем к ответу.
// Число инверсий (i < j, a[i] > a[j]) сортировкой слиянием; массив a[lo, hi) после вызова отсортирован
long long countInv(vector<long long>& a, int lo, int hi) {
if (hi - lo < 2) return 0;
int mid = (lo + hi) / 2;
long long res = countInv(a, lo, mid) + countInv(a, mid, hi);
// обе половины уже отсортированы: считаем пары (элемент слева, элемент справа)
int l = lo;
for (int r = mid; r < hi; r++) {
while (l < mid && a[l] <= a[r]) l++; // всё левее l — не больше a[r]
res += mid - l; // остальные левые строго больше a[r]
}
inplace_merge(a.begin() + lo, a.begin() + mid, a.begin() + hi); // обычное слияние
return res;
}
// Обгоны: finish[i] = i + v[i] * L; ответ — countInv(finish, 0, n)122:58 Сложность: сортировка слиянием работает за $O(n\log n)$ — делится на $\log n$ уровней, на каждом проход по всем блокам по одному разу, и дополнительный проход двумя указателями по тому же блоку порядка не меняет. Итого $O(n\log n)$.
124:07 Почему делим именно на две части? Так делается в сортировке слиянием. Инверсии можно считать и другими структурами данных, которые ещё не проходили.
a[l] <= a[r] сдвигает указатель). $a_i=i+v_i\cdot L$ может превысить $2\cdot10^9$, поэтому массив лучше хранить в long long.125:15 Задача F была разобрана на самой лекции по двум указателям, поэтому её пропустили.
125:48 Задача G. Дан массив из $N$ элементов; нужно найти кратчайший подотрезок, содержащий все различные значения массива (все $K$ различных). Сначала находим $K$ — число различных элементов, для этого кладём все $a_i$ в set и берём его размер. Дальше — обычная задача на два указателя (она тоже разбиралась на лекции): ищем минимальный подотрезок, в котором ровно $K$ различных значений.
// Длина кратчайшего подотрезка, содержащего все различные значения массива
int shortestAllDistinct(const vector<int>& a) {
int n = a.size();
int k = set<int>(a.begin(), a.end()).size(); // сколько всего различных значений
map<int,int> cnt;
int l = 0, best = n;
for (int r = 0; r < n; r++) {
cnt[a[r]]++;
while ((int)cnt.size() == k) { // в окне есть все значения — пробуем сжать слева
best = min(best, r - l + 1);
if (--cnt[a[l]] == 0) cnt.erase(a[l]);
l++;
}
}
return best;
}126:50 Есть $N$ игроков, каждый решал $M$ головоломок; даны $t_{ij}$ — время, за которое $i$-й игрок решил $j$-ю (матрица $N\times M$). Нужно для каждого игрока посчитать такую величину: перебираем все его головоломки; для головоломки со временем $x$ считаем, сколько элементов матрицы строго меньше $x$ во всех остальных строках (в своей строке не считаем). Сумма по всем его головоломкам — ответ для игрока.
131:46 Пример $3\times3$: первая строка $1,4,7$, вторая $2,5,8$, третья $3,6,9$. Для первой строки: для $1$ меньших в других строках нет — $0$; для $4$ меньше $2,3$ — их два; для $7$ меньше $2,3,5,6$ — четыре; сумма $6$. Аналогично для второй строки $1+3+5=9$, для третьей $2+4+6=12$.
134:48 Алгоритм. Строки должны быть отсортированы по возрастанию (если это не гарантируется — отсортируйте каждую). Ставим $N$ указателей, по одному на конец каждой строки.
137:44 На примере: максимальный из указателей — $9$ (третья строка); для него суммируем чужие указатели $(2+1)+(2+1)=6$ — вклад $6$ — и сдвигаем указатель третьей строки на элемент $6$. Теперь указатели на $7,8,6$: максимум $8$ из второй строки, затем $7$ из первой и так далее, как в «Стильной одежде». 139:48 Максимум может оставаться максимальным несколько итераций подряд — тогда его просто долго двигают влево.
// a[k][j] — время k-го участника на j-й головоломке (все значения различны).
// ans[k] — сумма по его головоломкам числа строго меньших значений в остальных строках.
vector<long long> puzzles(int n, int m, vector<vector<int>> a) {
for (auto& row : a) sort(row.begin(), row.end());
vector<int> p(n, m - 1); // p[k] — указатель на конец строки k
priority_queue<pair<int,int>> pq; // (значение под указателем, номер строки)
for (int k = 0; k < n; k++) pq.push({a[k][m - 1], k});
vector<long long> ans(n, 0), cntRow(n, m); // cntRow[k] — сколько элементов строки k ещё «живо»
long long alive = (long long)n * m; // всего «живых» элементов
while (!pq.empty()) {
auto [x, k] = pq.top(); pq.pop(); // самый большой из живых
ans[k] += alive - cntRow[k]; // все живые чужие элементы меньше x
alive--; cntRow[k]--; // x выходит из игры
if (--p[k] >= 0) pq.push({a[k][p[k]], k});
}
return ans;
}В коде сумма «живых» элементов в чужих строках равна alive - cntRow[k] — это и есть $\sum(l_q+1)$. Время: $O(NM\log N)$ с приоритетной очередью (на лекции максимум искали перебором указателей — $O(N)$ на шаг).
// То же с равными значениями: элементы с одинаковым значением обрабатываем группой
vector<long long> puzzlesTies(int n, int m, const vector<vector<int>>& a) {
vector<pair<int,int>> all;
for (int k = 0; k < n; k++)
for (int j = 0; j < m; j++) all.push_back({a[k][j], k});
sort(all.begin(), all.end());
vector<long long> ans(n, 0), cntRow(n, 0); // cntRow[k] — сколько элементов строки k строго меньше текущего значения
long long total = 0;
for (size_t i = 0, j; i < all.size(); i = j) {
j = i;
while (j < all.size() && all[j].first == all[i].first) j++;
for (size_t t = i; t < j; t++) ans[all[t].second] += total - cntRow[all[t].second];
for (size_t t = i; t < j; t++) { total++; cntRow[all[t].second]++; }
}
return ans;
}long long и $\ge$ в обоих проходах.