Подотрезок массива — несколько элементов, идущих подряд. Для массива $3,1,4,1,5,9$ набор $1,4,1$ — подотрезок, а $3,4,5$ — уже подпоследовательность (элементы не подряд). Сегодня работаем только с подотрезками; подотрезок с границами $l$ и $r$ обозначаем $[l, r]$.
Широкий класс задач олимпиадного программирования — что-то посчитать для подотрезков: подотрезок с максимальной суммой, подотрезок максимальной длины, в котором ровно $k$ различных элементов, и т. п. «В лоб» это двойной цикл:
for (int l = 0; l < n; ++l)
for (int r = l; r < n; ++r) {
// что-то считаем для отрезка [l, r]
// например: число различных элементов, ans = max(ans, r - l + 1)
}2:13 Оба цикла работают за $O(n)$, итого $O(n^2)$ (и ещё стоимость подсчёта на самом отрезке). Хочется за линию.
2:54 Пример: массив $2,1,3,2,4,1$, отрезок $1,3,2$. Сдвигая границы вправо постепенно, мы можем получить отрезок $3,2,4$ — такой «скользящий» переход и есть основа метода.
4:25 Нужно найти подотрезок максимальной длины, в котором не больше $K$ различных значений. Заводим левую границу $l$ и для окна $[l,r]$ — словарь cnt: cnt[x] — сколько раз $x$ встречается в текущем окне.
5:29 Разберём массив $1,2,1,3,4,2,3$ при $K=2$. Правая граница стоит на нулевом элементе — окно $\{1\}$, различных элементов один. Сдвигаем $r$: окно $1,2$ — два различных; ещё сдвиг: $1,2,1$ — по-прежнему два. Следующий сдвиг даёт $1,2,1,3$ — уже три различных, больше разрешённого $K$. Значит, окно надо сжимать слева, пока различных элементов снова не станет не больше $K$: $2,1,3$ — всё ещё три; $1,3$ — два, окно допустимо, можно снова двигать $r$.
map<int, int> cnt; // cnt[x] — сколько раз x в окне [l, r]
int l = 0, ans = 0;
for (int r = 0; r < n; ++r) {
cnt[a[r]]++; // добавили a[r] в окно
while ((int)cnt.size() > k) { // окно «плохое» — сжимаем слева
cnt[a[l]]--; // убрали a[l] из окна
if (cnt[a[l]] == 0)
cnt.erase(a[l]); // чтобы cnt.size() считало только присутствующие
l++;
}
ans = max(ans, r - l + 1); // окно [l, r] корректно
}a[r] число различных могло стать больше $K$. Если сдвигать $l$ вправо, окно только уменьшается и число различных в нём не увеличивается (либо уменьшается, либо остаётся прежним) — поэтому «сжимать слева» всегда правильный ход.erase), иначе cnt.size() не будет равен числу различных.while, окно $[l,r]$ корректно (различных не больше $K$). Задача на максимум длины, поэтому ответ пересчитываем как $r-l+1$.11:42 Решения таких задач выглядят одинаково: сначала правая граница добавляет элемент, потом левая сдвигается, пока окно «плохое», потом пересчитывается ответ. От задачи к задаче меняются только отдельные блоки:
sum += a[r], для различных — cnt[a[r]]++);sum -= a[l] или уменьшение счётчика);while — условие, нарушающее требование задачи (здесь «различных больше $K$»);l = 0
для r = 0..n-1:
добавить a[r] в окно
пока окно плохое:
удалить a[l] из окна
l++
обновить ответ по окну [l, r]14:30 Хотя внутри внешнего цикла есть ещё цикл, за всю программу $r$ пройдёт от $0$ до $n$ ровно $n$ шагов (она только растёт). Указатель $l$ тоже только увеличивается — нигде нет l-- — и поэтому за всю программу сделает не более $n$ шагов. Внутренний while делает шаги не «на каждой итерации по $n$», а суммарно не более $n$ за всё время. Итого $n + n = O(n)$ шагов.
mapmap, его операция стоит $O(\log n)$, поэтому полное время — $O(n\log n)$. Если заменить map на unordered_map (в среднем $O(1)$ на операцию), получим линейное время.while, а не ifif, то на каждый шаг $r$ левая граница сдвигалась бы не более чем на единицу. Но уже на разобранном примере, чтобы получить допустимое окно, нужно сдвинуть $l$ сразу на две позиции при одном $r$. Поэтому сдвиг — обязательно в цикле while, и условие в нём — то, что делает окно плохим.17:14 Про корректность ответа: внутри while всегда пишем условие «плохо» (здесь — различных больше $K$), т. е. противоположное тому, что требует задача. На момент обновления ответа окно $[l,r]$ уже корректно, и посчитанная величина (сумма, cnt, …) относится именно к нему — повторно ничего считать не нужно.
map в C++ 20:4420:44 map — «коробка» с парами «ключ → значение», словарь. Подключается через #include <map>:
map<string, int> cnt; // ключ — string, значение — int
cnt["aba"] = 2; // положили пару ("aba", 2)
cnt["aba"]++; // изменили значение: стало 3int, double, string, …); со значением можно делать всё, что с обычной переменной.map пустой. Если обратиться к ключу, которого нет, он создаётся со значением $0$. Поэтому cnt[x]++ сразу работает для нового $x$.cnt.size() — число ключей, т. е. число различных элементов в окне — при условии, что ключи с нулевым счётчиком удалены через erase.24:53 Нужно найти подотрезок максимальной длины, где все элементы различны. Для массива $1,2,3,1,2,4$ ответ — $3,1,2,4$ (длина 4). Решаем тем же методом: словарь cnt, левая граница $l=0$, ответ $0$ (изначально).
map<int, int> cnt;
int l = 0, ans = 0;
for (int r = 0; r < n; ++r) {
cnt[a[r]]++; // добавили a[r]
while (cnt[a[r]] > 1) { // в окне появился дубликат a[r]
cnt[a[l]]--;
l++;
}
ans = max(ans, r - l + 1);
}while — «cnt[a[r]] > 1».map — удалять ключи не обязательно.ans больше нуля, а дальше он увеличивается при нахождении более длинного.32:53 Пример: для $K=2$ нужно найти самый длинный подотрезок, содержащий не более двух нулей (в разобранном на лекции массиве такой подотрезок имел длину 5). Структура кода та же, меняются только добавление/удаление элемента:
int zeros = 0, l = 0, ans = 0;
for (int r = 0; r < n; ++r) {
if (a[r] == 0) zeros++; // добавление a[r]
while (zeros > k) { // слишком много нулей
if (a[l] == 0) zeros--; // удаление a[l]
l++;
}
ans = max(ans, r - l + 1);
}35:00 Блоки «добавить элемент» и «удалить элемент» здесь отличаются от предыдущих задач (нужен только счётчик нулей, а не словарь), но весь остальной каркас остался прежним.
lower_bound и upper_bound 36:2336:23 Функции из библиотеки <algorithm>. В них передаются указатель (итератор) на начало и на конец подотрезка и число $x$; подотрезок обязательно должен быть отсортирован по возрастанию.
lower_bound(a.begin(), a.end(), x) — возвращает итератор на первый элемент, не меньший $x$ (т. е. $\ge x$);upper_bound(a.begin(), a.end(), x) — итератор на первый элемент, строго больший $x$.38:25 Чтобы из итератора получить значение, перед ним ставят звёздочку: *lower_bound(...).
lower_bound тоже указал бы на первую семёрку, а upper_bound — на $8$.39:05 Пример применения. Есть два отсортированных массива $A$ и $B=2,3,6,8,12$. Для каждого $a_i$ найти в $B$ первый элемент, не меньший $a_i$: для $a_i=7$ это $8$.
for (int i = 0; i < n; ++i) {
int x = *lower_bound(b.begin(), b.end(), a[i]); // первый элемент B, не меньший a[i]
// для a[i] = 7 получим x = 8
}lower_bound вернёт b.end(), и разыменовывать такой итератор нельзя. Это замечание — собственное дополнение: на лекции граничный случай не разбирался.41:10 Зачем две похожие функции? Например, чтобы найти границы подотрезка из семёрок в отсортированном массиве: lower_bound(7) даёт его начало, upper_bound(7) — место сразу после него. Количество семёрок — разность этих итераторов.
42:32 Метод работает и там, где нет подотрезков. Задача: в отсортированном массиве найти два числа с заданной суммой $S$. Пример на лекции: $S=15$, массив $1,2,4,7,11,15$. Ставим $l$ в начало и $r$ в конец и сдвигаем их навстречу друг другу.
Описание на лекции в записи фрагментарное, поэтому ниже — полный корректный разбор.
int l = 0, r = n - 1;
while (l < r) {
int s = a[l] + a[r];
if (s == S) { /* нашли пару (l, r) */ break; }
if (s < S) l++;
else r--;
}43:55 Задача про количество пар с суммой не больше (или ровно) заданной решается в той же идее: двигаем указатели, пока соответствующее условие нарушено, а когда остановились — все элементы между указателями дают подходящие пары, которые можно посчитать разностью индексов.
long long cntPairs = 0;
int l = 0, r = n - 1;
while (l < r) {
if (a[l] + a[r] <= S) { cntPairs += r - l; l++; }
else r--;
}45:17 Для массива $a=3,1,4,2,5$ построим массив pref: pref[i] — сумма элементов $a_0,\dots,a_i$. Тогда $pref_0=a_0$, $pref_1=3+1=4$, $pref_2=8$, $pref_3=10$, $pref_4=15$.
pref[0] = a[0];
for (int i = 1; i < n; ++i)
pref[i] = pref[i - 1] + a[i];47:22 Почему так: в $pref_r$ лежит вся сумма от начала до $r$, в $pref_{l-1}$ — сумма от начала до $l-1$. Вычитая вторую из первой, получаем ровно сумму на $[l,r]$. Значит, после предподсчёта за $O(n)$ сумма на любом подотрезке берётся за $O(1)$.
48:47 Это тоже «два указателя», но в другой реализации. Перебираем правую границу $r$; для неё выгоднее всего взять такое $l$, при котором $pref_{l-1}$ минимально среди всех $l\le r$: тогда $pref_r - pref_{l-1}$ максимально. Поэтому поддерживаем минимум префиксных сумм слева.
long long ans = LLONG_MIN, minSum = 0; // minSum — минимум pref[l-1] по уже рассмотренным l
for (int r = 0; r < n; ++r) {
ans = max(ans, pref[r] - minSum); // лучший подотрезок, заканчивающийся в r
minSum = min(minSum, pref[r]); // теперь r годится как «l-1» для следующих
}51:29 Левая граница $l$ в коде не хранится явно: нам важно лишь значение минимума, а минимум по префиксам считается так же, как минимум в обычном массиве (обновляем при каждом новом элементе).
minSum = 0 соответствует «пустому префиксу» $pref_{-1}=0$ — подотрезку, начинающемуся с нулевого элемента. Без него потерялись бы подотрезки, начинающиеся в начале массива. Начальное значение ans — минус бесконечность, иначе при массиве из одних отрицательных чисел вышел бы ответ $0$ (пустой подотрезок), которого условие обычно не допускает.52:50 Заводим cur — максимальную сумму подотрезка, заканчивающегося в текущем элементе. Переходя к следующему элементу $a_i$, у него два варианта: приклеить его к лучшему подотрезку, заканчивающемуся в $i-1$, либо начать новый подотрезок с самого $a_i$.
long long cur = a[0], ans = a[0];
for (int i = 1; i < n; ++i) {
cur = max(cur + a[i], (long long)a[i]); // продолжить или начать заново
ans = max(ans, cur); // cur верен только для текущего i — сразу запоминаем
}63:07 Почему достаточно двух вариантов: любой подотрезок, заканчивающийся в $i$, либо состоит из одного $a_i$, либо получается приклеиванием $a_i$ к подотрезку, заканчивающемуся в $i-1$. Среди вторых лучший по сумме — тот, у которого максимальна сумма $cur_{i-1}$, поэтому других кандидатов нет. Подотрезки, не заканчивающиеся в $i$, учтены на более ранних шагах через $ans$.
55:34 Часто нужно не только число, но и границы $l$ и $r$ нужного подотрезка. Для этого рядом с ответом сохраняем границы и обновляем их, когда нашли ответ лучше. Пример: найти подотрезок максимальной длины с суммой не больше $K$.
long long sum = 0;
int l = 0, ans = 0, ansL = 0, ansR = -1; // ansL, ansR — границы лучшего найденного
for (int r = 0; r < n; ++r) {
sum += a[r]; // добавили
while (sum > k) { // сумма слишком велика
sum -= a[l];
l++;
}
if (r - l + 1 > ans) { // нашли отрезок лучше — запоминаем границы
ans = r - l + 1;
ansL = l;
ansR = r;
}
}
// подотрезок — a[ansL..ansR]64:28 Задачи А (пузырьковая) и Б (вставками) — прямая реализация сортировок, разобранных на предыдущей лекции; задача D — сортировка подсчётом, задача G — слиянием (были на лекции). Ниже — остальные.
65:50 Дано $n$ ($n\le 10^5$) пар (идентификатор, очки). Упорядочить по убыванию очков, а при равенстве очков — по возрастанию идентификатора. Квадратичные сортировки не пройдут, поэтому используем встроенную sort из <algorithm>. Два способа.
67:11 Способ 1: с компаратором. Компаратор — своя функция сравнения, которую передают третьим аргументом. Она получает два элемента и возвращает true, если первый должен стоять раньше второго. По умолчанию пары сортируются по возрастанию первого элемента, при равенстве — по возрастанию второго.
vector<pair<int,int>> v(n); // (id, score)
for (auto &p : v) cin >> p.first >> p.second;
bool cmp(pair<int,int> a, pair<int,int> b) { // функция объявляется вне main
if (a.second != b.second) return a.second > b.second; // очки по убыванию
return a.first < b.first; // при равенстве id по возрастанию
}
sort(v.begin(), v.end(), cmp);72:46 Способ 2: без компаратора. Переставим элементы пары и умножим очки на $-1$: храним $(-score, id)$. Сортировка пар по возрастанию сначала упорядочит по $-score$ (то есть по убыванию $score$), при равенстве — по $id$. При выводе знак возвращаем.
vector<pair<int,int>> v(n); // (-score, id)
for (auto &p : v) {
int id, sc; cin >> id >> sc;
p = {-sc, id};
}
sort(v.begin(), v.end());
for (auto &p : v) cout << p.second << " " << -p.first << "\n";74:54 Две строки $A$ и $B$ — анаграммы, если одна получается перестановкой букв другой (например, «шарм» и «марш»). Два способа.
sort(s.begin(), s.end())) и сравнить на равенство. Время $O(n\log n)$.vector<int> count(const string &s) {
vector<int> c(26, 0);
for (char ch : s) c[ch - 'a']++;
return c;
}
bool isAnagram(const string &a, const string &b) {
return count(a) == count(b); // векторы сравниваются целиком
}78:55 По сути первый способ — это сортировка подсчётом без восстановления строки. Строка — это вектор символов, поэтому к ней применимы все методы обычных векторов.
80:21 Дан массив из $n$ чисел; известно, что разность между максимумом и минимумом не превосходит $10^7$. Нужно отсортировать массив, $n$ велико. Используем сортировку подсчётом, но с смещённой точкой отсчёта: находим минимум $mn$ массива и считаем счётчики по индексу $a_i - mn$.
int mn = *min_element(a.begin(), a.end());
vector<int> cnt(MAXD + 1); // MAXD = 10^7: размах значений
for (int x : a) cnt[x - mn]++; // индекс — отклонение от минимума
// восстановление: значение = индекс + mn
int pos = 0;
for (int v = 0; v <= MAXD; ++v)
while (cnt[v]--) a[pos++] = v + mn;83:48 Дана строка. Составить из неё (можно не использовать часть букв) самый длинный палиндром, а среди всех таких — лексикографически наименьший. Например, aab → aba. Палиндром читается одинаково слева направо и справа налево.
85:11 Палиндром состоит из двух зеркальных половинок и, возможно, одного «центрального» символа $X$ (нечётная длина). Поэтому все буквы, кроме $X$, должны встречаться парами. Считаем count[26]; в половинку кладём каждую букву по count[c]/2 раз, перебирая буквы по возрастанию — это даёт лексикографически минимальную половинку. Центральный символ — наименьшая буква, встречающаяся нечётное число раз (если такая есть).
string half;
int mid = -1;
for (int c = 0; c < 26; ++c) {
half.append(cnt[c] / 2, 'a' + c); // cnt[c]/2 копий буквы
if (mid == -1 && cnt[c] % 2 == 1) mid = c; // наименьшая буква с нечётным счётом
}
string rev(half.rbegin(), half.rend());
string ans = half;
if (mid != -1) ans += char('a' + mid);
ans += rev;cnt[c]/2 копий каждой буквы. Значит, два палиндрома максимальной длины с одинаковыми половинками различаются только центральным символом и зеркальной частью после него, а первое различие — в центре. Меньший палиндром получается при наименьшем центре. Метод append(count, ch) добавляет count копий символа — обычное умножение строки на число в C++ не работает.89:18 Дана карта из $n\times m$ чисел — стоимостей заказов $a_i$ (двумерность не важна, считываем в один массив) и несколько роверов; у ровера есть «жадность» $b_j$, и он может выполнить только заказ со стоимостью $a_i \ge b_j$. Каждый заказ достаётся не более чем одному роверу. Максимизировать число выполненных заказов.
91:19 Сортируем и заказы, и роверов по возрастанию и идём двумя указателями: один по роверам, другой по заказам. Если текущий заказ подходит роверу ($a_i\ge b_j$) — назначаем и двигаем оба указателя; иначе пропускаем этот заказ (он слишком дешёвый и для остальных, более жадных роверов тоже не подойдёт) и двигаем только указатель по заказам.
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0, cnt = 0;
while (i < (int)a.size() && j < (int)b.size()) {
if (a[i] >= b[j]) { cnt++; i++; j++; } // заказ подходит роверу — назначаем
else i++; // заказ слишком дешёвый — пропускаем
}94:06 Строим пирамиду. На вершине — храм (он тоже один из уровней), под ним идут уровни; для устойчивости разность длин оснований соседних уровней должна быть не меньше $3$. Есть нижнее ограничение $x$ на сторону храма и набор доступных блоков. Максимизировать число уровней.
95:30 Сортируем размеры по неубыванию. Находим первый элемент, не меньший $x$ (lower_bound) — это храм. Дальше двигаемся указателем вправо и берём уровень, если его размер хотя бы на $3$ больше размера последнего взятого. Храм входит в ответ.
sort(a.begin(), a.end());
int i = lower_bound(a.begin(), a.end(), x) - a.begin(); // храм
if (i == n) { cout << 0; return 0; } // подходящего храма нет
int last = a[i], cnt = 1;
for (int j = i + 1; j < n; ++j)
if (a[j] - last >= 3) { cnt++; last = a[j]; }96:54 Физически «стирать» взятый элемент не нужно: мы просто двигаем указатель вправо, а разность считаем относительно последнего взятого уровня.
98:18 Есть набор строк — «кусков» десятичного числа. Расставить их в таком порядке, чтобы после склейки получилось максимально возможное число. Пример: куски $20$, $04$, $66$ (строки могут начинаться с нуля). Склейка в порядке $20,04,66$ даёт $200466$, а лучше поставить $66$ первым, затем $20$, затем $04$ — получим $662004$.
100:27 Гипотеза «сначала лексикографически большие» неверна: если у одной строки префикс совпадает с другой, длиннее считается большей, и мы можем поставить «99 и много нулей» раньше «99…», хотя поменяв их местами, получили бы число больше.
103:22 Доказательство от противного: пусть в «оптимальном» порядке нашлась пара кусков, для которой условие не выполнено: $A$ стоит раньше $B$, но $AB<BA$. Тогда если поменять их местами, то (при соседстве) число станет больше — значит порядок не был оптимальным. Противоречие.
vector<string> s(n);
sort(s.begin(), s.end(), [](const string &a, const string &b) {
return a + b > b + a; // a должна стоять раньше b
});
for (auto &x : s) cout << x;106:21 Числа в int не конвертируем: длина склейки огромна, она не влезет ни в какой целочисленный тип, поэтому работаем только со строками.
sort работал корректно, компаратор должен задавать строгий слабый порядок (в частности, быть транзитивным). Сравнение «$a+b>b+a$» именно таким и является: оно эквивалентно сравнению дробей $\dfrac{a}{10^{|a|}-1}$ и $\dfrac{b}{10^{|b|}-1}$ (бесконечные периодические десятичные дроби с периодами $a$ и $b$), а сравнение чисел транзитивно.107:01 Дан набор многоугольников на плоскости (возможно, невыпуклых, с разным числом вершин), гарантируется, что любые два из них вложены друг в друга и их границы не пересекаются и не касаются. Для каждого нужно вывести, во сколько многоугольников он вложен (для самого внешнего — $0$).
110:01 Идея: если один многоугольник вложен в другой, то его самая правая точка (наибольший $x$) строго левее самой правой точки внешнего. Поэтому достаточно найти в каждом многоугольнике самую правую вершину и отсортировать многоугольники по убыванию этой координаты, помня исходный индекс (чтобы вывести ответ в порядке входа). Тогда номер в отсортированном порядке — глубина вложенности: у самого внешнего $0$, у следующего $1$ и т. д.
112:04 На этом разбор закончен. Контест по двум указателям уже опубликован; дедлайн объявят после следующего контеста.