0:10 Лекция — про неочевидные, но очень практичные вещи в C++, которые пригодятся в олимпиадах: как правильно вводить и выводить данные, какие функции есть в стандартной библиотеке, лямбды, препроцессор, случайные числа, санитайзеры, стресс-тестирование и отладчик. После перерыва — разбор двух контестов по строкам и хэшам.
0:37 По C++ есть очень хороший справочник cppreference.com. В нём расписано почти всё, что может пригодиться: если загуглить, например, set, первой ссылкой, скорее всего, будет именно он, а внизу страницы обычно есть примеры. Очень удобно, чтобы что-то узнавать и вспоминать.
1:33 Напомним две строки, которые стоит писать в начале main:
ios::sync_with_stdio(false);
cin.tie(nullptr);1:57 Что делает первая. В C++ есть два вида потоков ввода-вывода: потоки C++ (cin, cout) и потоки C (scanf, printf). По умолчанию они синхронизированы — не работают в случайном порядке друг относительно друга. Если синхронизацию отключить, всё начинает работать сильно быстрее. Побочный эффект: после sync_with_stdio(false) нельзя смешивать cout и printf в одной программе — символы будут перемешиваться.
2:21 Что делает вторая. cin.tie(...) — это «привязка» потока: по умолчанию cin привязан к cout. На практике это значит, что перед каждым чтением из cin программа вызывает cout.flush(). Строка cin.tie(nullptr) говорит, что cin теперь ни к чему не привязан.
3:04 Что такое flush. Программа взаимодействует с системой, и это взаимодействие — узкое место, которое занимает много времени: записать что-то в файл, в память или в поток вывода долго. Поэтому на практике вывод записывается во временный буфер — место, куда запись быстрая. Буфер накапливает то, что вы выводите, и в какой-то момент сбрасывается: всё, что в нём лежит, целиком отдаётся системе. Сам сброс буфера (flush — «смыть») — тяжёлая операция. Если делать cout.flush() после каждого символа или вывода, программа будет работать очень долго.
4:28 Чтобы чередовать cin и cout и всё работало быстро, мы отвязываем cin от cout. Тогда после вывода текст не обязательно сразу выводится: он выведется, когда буфер закончится или когда программа завершится. 4:42 Иногда пишут ещё cout.tie(nullptr) — это смысла не имеет: cout по умолчанию и так ни к чему не привязан.
5:00 Вопрос: можно ли не писать cin.tie в интерактивных задачах? Скорее всего, да, но лучше писать. 5:20 В интерактивных задачах обычно в условии сказано, что после каждого вашего вывода нужно сбрасывать буфер, чтобы интерактор получил то, что вы ему отправили: вы пишете вопрос в cout, и интерактор должен его увидеть. Для этого есть два варианта: cout << flush или endl.
endl и '\n''\n' — это просто символ перевода строки; endl — это перевод строки плюс flush. Если в обычной (не интерактивной) задаче писать endl каждый раз, программа будет работать долго, потому что вы сбрасываете буфер на каждой строке. Поэтому не в интерактивных задачах пишем '\n', а в интерактивных — flush или endl; для надёжности преподаватель советует делать сброс после каждого вывода.printf и scanf 6:436:57 Это потоки C. Использовать их стоит, когда нужен удобный форматированный ввод или вывод. printf принимает первым аргументом строку формата — статичные символы и места подстановки, — а следующими аргументами переменные, которые подставляются на эти места. Переменные вставляются после знака % и спецификатора, задающего тип и формат.
%d — int (decimal);%f — вещественное число; точность задают после процента: %.7f — семь знаков после запятой;%lf — double (в scanf нужен именно он), %lld — long long.9:40 scanf считывает. Первый аргумент — тоже строка формата, а дальше передаются не значения, а адреса переменных: scanf("%d", &x). 10:14 Если написать просто x, передастся значение x, scanf попытается записать по адресу, равному значению x (например, по адресу $10$), и всё сломается. Поэтому знак & обязателен.
10:38 Ещё одно удобство форматов: если время записано как «часы:минуты.секунды», то в строке формата разделители указываются прямо в ней — парсить их вручную не нужно:
#include <bits/stdc++.h>
int main() {
int x = 10; double d = 3.14159265358979; long long big = 1234567890123LL;
printf("%d\n", x); // int
printf("%.7f\n", d); // double, 7 знаков после запятой
printf("%lld\n", big); // long long
int h, m, s;
sscanf("12:34.56", "%d:%d.%d", &h, &m, &s); // разделители разбирать вручную не нужно
printf("%02d:%02d.%02d\n", h, m, s);
int y; double z;
sscanf("7 2.5", "%d %lf", &y, &z); // scanf принимает АДРЕСА переменных; для double — %lf
printf("%d %.1f\n", y, z);
}cout 11:3811:53 В задачах часто просят вывести число с какой-то точностью. В cout, помимо самих данных, можно подавать модификаторы потока, которые говорят ему работать так или иначе.
fixed: по умолчанию вещественные числа могут выводиться в научном формате (например, 1e+10 — экспонента задаёт сдвиг), что обычно приводит к неверному ответу. fixed заставляет выводить всегда в привычном виде.setprecision(k) (из <iomanip>) задаёт количество знаков после запятой (вместе с fixed).cout << fixed << setprecision(7); // один раз в начале программы
cout << 1.0 / 3 << "\n"; // 0.333333313:23 Эти модификаторы работают до тех пор, пока их не отменят, поэтому достаточно написать их один раз в начале программы. 13:58 На вопрос «как отключить setprecision» преподаватель ответила, что не знает и что подключать его обратно вам не понадобится.
setprecision округляет, а не отбрасываетfixed и setprecision(2) число $1.239$ выводится как 1.24, а не 1.23. Из-за двоичного представления вещественных чисел результат на «полуцелых» значениях может быть неожиданным: $2.675$ выводится как 2.67, $0.125$ — как 0.12 (при точном равенстве округляется к чётному). Учитывайте это при сравнении с эталоном.15:51 Иногда нужно читать из файла и писать в файл. Есть два способа.
15:54 Способ 1: freopen. Функции передают имя файла, режим открытия и поток, к которому «привязать» файл. Режимы: "r" — чтение, "w" — запись (есть ещё дозапись в конец и бинарный). Для чтения привязываем к stdin (стандартный поток ввода), для записи — к stdout. После этого обычные cin и cout работают только с этими файлами. Так удобно перенести программу целиком на файлы.
#include <bits/stdc++.h>
using namespace std;
int main() {
// способ 1: перенаправляем стандартные потоки на файлы — дальше cin/cout работают с ними
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int a, b; cin >> a >> b;
cout << a + b << "\n";
return 0;
}17:02 Способ 2: ifstream и ofstream (из библиотеки <fstream>) — если нужно перенаправить часть ввода-вывода. ifstream — input file stream: такой же поток, как cin, но его надо проинициализировать именем файла. Объект называют как угодно (in, abc…), и он работает как cin/cout: in >> x, out << x.
#include <bits/stdc++.h>
using namespace std;
int main() {
// способ 2: отдельные объекты-потоки; cin и cout остаются нетронутыми
ifstream in("input.txt"); // input file stream
ofstream out("output.txt"); // output file stream
int a, b;
in >> a >> b; // как cin
out << a + b << "\n"; // как cout
cout << "done\n"; // консоль по-прежнему доступна
}18:32 По мнению преподавателя, лучше использовать первый способ: в втором легко забыть, что вы пишете в файл, и случайно написать в cout — всё перемешивается. 19:00 Нельзя «переопределить» cin/cout создав свою переменную с тем же именем: она будет локальной, а в других функциях останется глобальный cin — две переменные с одним названием, так делать плохо.
stringstream и getline 19:4219:46 Очень удобная штука — stringstream из библиотеки <sstream>. Если у вас есть строка, которую нужно разобрать на отдельные объекты, пропуская всякие пробелы и переносы, то создаётся istringstream от этой строки, и дальше читаем из неё операциями >> точно так же, как из cin — случайное количество пробелов, табуляций и переносов он аккуратно убирает.
21:38 ostringstream работает как cout: в него можно писать переменные и аккуратно собирать строку; затем os.str() возвращает результат. 22:30 stringstream работает со строкой, а не с файлом; если нужно разбирать файл, используют ifstream: он так же разбирает всё по пробелам и переносам.
#include <bits/stdc++.h>
using namespace std;
int main() {
string line = " 12 abc\t3.5 ";
istringstream ss(line); // поток, читающий из строки
int a; string w; double d;
ss >> a >> w >> d; // лишние пробелы и табуляции пропускаются сами
cout << a << "|" << w << "|" << d << "\n";
ostringstream os; // поток, пишущий в строку
os << "x=" << 5 << ", y=" << 2.5;
string res = os.str(); // собранная строка
cout << res << "\n";
}22:56 getline. Если данные заданы в неудобном формате, иногда нужно считывать строки целиком — например, когда пробелы важны и выкидывать их нельзя. getline(cin, s) принимает поток и строку, куда записать, и читает строку со всеми пробелами до первого перевода строки. Цикл while (getline(cin, s)) работает, пока удаётся считать строку.
cin >> и getlinecin есть «указатель» на место, где он сейчас стоит. После cin >> n для входа «12⏎ 123 ...» указатель стоит ровно после «12», перед переводом строки. Если сразу вызвать getline, он увидит перевод строки и вернёт пустую строку. Поэтому, когда формат ввода — число $n$, а затем $n$ строк с пробелами, нужно после чтения числа вызвать cin.ignore() — он пропустит остаток строки и переведёт указатель на следующую. 25:26 Про это важно не забывать.#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n; // после чтения числа указатель стоит прямо перед '\n'
cin.ignore(); // пропускаем остаток первой строки, иначе первый getline вернёт пустую строку
for (int i = 0; i < n; i++) {
string s;
getline(cin, s); // читает строку целиком, вместе с пробелами, до '\n'
cout << "[" << s << "]\n";
}
}26:24 Функции из стандартной библиотеки лежат в разных заголовках; по подсказкам среды (или по сообщению компилятора) можно понять, какой подключить. Забыть их легко из-за того, что они используются редко, но запомнить стоит основные; остальные полезны, но опциональны. Если подключить <bits/stdc++.h>, то задумываться об этом не нужно: он включает почти все заголовки (это нестандартный заголовок GCC, но он есть на большинстве олимпиадных систем).
27:31 Для чисел есть std::gcd и std::lcm (в C++17, заголовок <numeric>), а также старая функция __gcd. 28:29 Если по какой-то причине писать НОК руками, то формула $\operatorname{lcm}(a,b)=\dfrac{ab}{\gcd(a,b)}$ плохо тем, что произведение $ab$ может переполниться. Правильно — сначала делить $a$ на НОД (он точно делится), а потом умножать на $b$: тогда, если итоговый результат помещается в тип, внутри переполнения не случится.
// gcd/lcm (C++17, <numeric>); lcm вручную — сначала делим, потом умножаем, чтобы не переполниться
long long a = 1000000000000LL, b = 999999999989LL;
long long g = std::gcd(a, b);
long long l = a / g * b; // а не a * b / g30:42 У стандартных контейнеров есть итераторы: v.begin(), v.end(). Итераторы работают в полуинтервалах: v.end() — элемент после последнего. С итераторами удобно работать, потому что на них можно звать стандартные функции независимо от контейнера: на строке, на векторе и на чём-то ещё.
31:28 Например, min_element(v.begin(), v.end()) (заголовок <algorithm>) возвращает итератор на минимальный элемент. Чтобы получить значение, итератор разыменовывают: *it. 32:12 Чтобы получить позицию минимального элемента, итераторы вычитают: it - v.begin() (для вектора это $O(1)$, для сложных контейнеров — за линию). Аналогично есть max_element. 32:48 Если нужно искать не на всём массиве, а на отрезке $[l,r)$, пишут v.begin() + l и v.begin() + r; $l$ и $r$ — целые числа. 33:16 max_element и min_element работают за линию — это просто удобное сокращение, чтобы не писать цикл каждый раз.
nth_element 33:3933:45 nth_element принимает два итератора и ещё одно число — позицию $k$. Она считает $k$-ю порядковую статистику: если массив отсортировать и взять $k$-е число, это и будет $k$-я порядковая статистика. Но этим она не ограничивается: она ставит это число на свою позицию, а все остальные элементы разбивает на две части — меньшие (они лежат до позиции $k$) и большие (после). Обе части не отсортированы: внутри каждой элементы лежат в произвольном порядке. Функция ничего не возвращает — результат лежит в массиве.
vector<int> w = {9, 4, 7, 1, 8, 3, 6, 2, 5};
int k = 4; // индекс (с нуля) искомого элемента в отсортированном массиве
nth_element(w.begin(), w.begin() + k, w.end());
// теперь w[k] == 5; все элементы левее не больше 5, все правее — не меньше36:01 Работает она за $O(n)$ в среднем — то есть быстрее сортировки: можно, конечно, отсортировать массив и взять нужный элемент, но есть рандомизированный алгоритм, который находит порядковую статистику в среднем за $O(n)$ и ещё и разбивает массив на две части. 36:46 В худшем случае, насколько понимает преподаватель, такое решение может работать за квадрат.
w.begin() + k ставит на место тот элемент, который был бы по индексу $k$ после сортировки. Если нужен «$k$-й по порядку» при счёте с единицы, передавайте w.begin() + (k - 1); на лекции из-за этого говорили про $k-1$ элементов слева и $n-k$ справа. Алгоритм, на котором она основана, называют quickselect.sort и stable_sort 37:2137:27 sort(v.begin(), v.end()) сортирует отрезок — в том числе можно отсортировать подотрезок v.begin() + l…v.begin() + r за его размер. 37:44 stable_sort сохраняет порядок равных элементов. Пусть v — массив пар $(1,1),(2,3),(2,4),(1,0),(2,2)$, и мы сортируем только по первому элементу. Обычный sort считает пары с равными первыми элементами равными и разрешает себе расположить их в любом порядке — например, поставить $(2,4)$ раньше $(2,3)$. stable_sort оставит их в исходном порядке: $(2,3),(2,4),(2,2)$. 39:07 Это полезно, когда в структуре с переопределённым оператором «меньше» сравнивается одно поле, а остальные поля нужно оставлять в прежнем порядке.
sortsort «в теории может отработать за линию», а stable_sort всегда за $O(n\log n)$. Это неточно: sort в стандартной библиотеке гарантированно работает за $O(n\log n)$ в худшем случае (внутри — introsort), быстрее чем за $n\log n$ сравнением сортировать нельзя. stable_sort тоже $O(n\log n)$ (при достаточной дополнительной памяти) и на практике работает примерно так же быстро.merge и inplace_merge 40:1440:17 merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()) принимает два отсортированных отрезка и сливает их в третий; работает за сумму размеров (два указателя, как в сортировке слиянием). Например, при a = {1,2,3}, b = {4} получим c = {1,2,3,4}.
41:29 Важный момент: merge не меняет размер c. Нужно заранее выделить место (c.resize(...) или вектор нужного размера), иначе, дойдя до конца c, программа выйдет за границы — будет ошибка. Можно начинать писать с произвольной позиции (c.begin() + L), главное, чтобы места хватило. 42:34 Для случая, когда нужно просто добавлять в конец, есть «вставляющий итератор» back_inserter(c) — он делает push_back каждый раз.
43:18 Можно ли слить $A$ и $B$ прямо в $A$? Напрямую — нет (в merge результат пишется в другой диапазон). Для случая, когда два отсортированных куска лежат подряд в одном массиве, есть inplace_merge(first, middle, last): он сливает [first, middle) и [middle, last) в этом же диапазоне. Преподаватель на лекции не была уверена, как он устроен, и отправила прогуглить; в итоге именно такое поведение у inplace_merge.
vector<int> a = {1, 2, 3}, b = {4}, c;
merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c)); // c = {1, 2, 3, 4}; размер c растёт сам
vector<int> d(4); // или заранее выделяем место
merge(a.begin(), a.end(), b.begin(), b.end(), d.begin());
vector<int> e = {1, 4, 6, 2, 3, 5}; // два отсортированных куска подряд
inplace_merge(e.begin(), e.begin() + 3, e.end()); // e = {1, 2, 3, 4, 5, 6}fill, copy, assign, iota 44:55fill(begin, end, x) проходит по отрезку и присваивает значение. Очень удобно «обнулять» и пересоздавать ничего не нужно.copy(first, last, dest) копирует отрезок в новое место, начиная с итератора dest. Как и у merge, место должно быть заранее: размер не меняется; если места не хватит — ошибка. Всё это можно вызывать на подотрезках: нужно передать правильные итераторы.v.assign(n, x) пересоздаёт вектор с новым размером и заполняет значением. В отличие от него, fill заполняет уже имеющийся вектор (или его отрезок) и размер не меняет.memset/memcpy 47:1447:14 Всё, что говорилось выше, относится к контейнерам с итераторами (вектор и т. п.). Но те же функции работают и с обычными массивами: вместо итераторов передают указатели, например fill(a + 1, a + 10, x). 47:55 Имя массива a хранит указатель на его начало, а с указателями можно делать арифметику: a + 1 — второй элемент (счёт с нуля, «на один элемент вперёд»), a + 10 — это «после конца» отрезка из десяти элементов (полуинтервал). Таким образом sort, merge и остальные функции можно писать на массивах: sort(a, a + n).
48:35 Вопрос: зачем copy, если можно написать b = a? copy работает на подотрезках: можно скопировать часть массива в новое место.
49:23 Из чата подсказали ещё одну полезную функцию — iota(begin, end, x0) (заголовок <numeric>): она заполняет отрезок возрастающими значениями $x_0,x_0+1,\dots$ — например, $0,1,2,3,\dots$; внутри это просто присваивание значения и затем ++, так что нужен лишь оператор ++ у типа.
50:31 Есть ещё «сишные» функции memset и memcpy — аналоги fill и copy, которые работают только с массивами и с итераторами не работают.
memset(a, value, size): принимает указатель на начало, значение и размер в байтах; заполняет байты значением (однобайтовым). Поэтому, например, memset(a, 0, 2) для массива int заполнит лишь половину одного int. Чтобы заполнить массив целиком, пишут n * sizeof(int) (или просто sizeof(a)). sizeof принимает тип данных и возвращает его размер в байтах (у каждого типа он фиксирован).char или маленькое int). На практике memset почти всегда используют для заполнения нулём.memcpy(dest, src, bytes) копирует отрезок байт из одного места в другое; dest — куда, src — откуда, размер снова в байтах.54:50 Преимущество над fill и copy действительно есть: это низкоуровневые функции, которые работают напрямую с байтами и поэтому быстрее, но пользоваться ими неудобно.
memset заполняет байты, для массива int безопасны только значения $0$ (все байты нули) и $-1$ (все байты 0xFF): memset(a, 1, sizeof a) даёт в каждой ячейке 0x01010101 = 16843009, а не $1$ (проверено запуском). Популярное «бесконечное» значение — memset(a, 0x3f, sizeof a) (ячейки становятся $1061109567$).reverse и rotate 55:2155:29 reverse(begin, end) разворачивает отрезок (в том числе подотрезок). 55:37 rotate(begin, middle, end) делает циклический сдвиг так, чтобы элемент, на который указывает middle, оказался первым: после rotate идут элементы [middle, end), потом [begin, middle). Например, {0,1,2,3,4,5} при middle = begin + 2 превращается в {2,3,4,5,0,1}.
unique и сжатие координат 56:2656:26 Очень полезная функция. Часто приходится сжимать координаты: когда координаты даны до $10^9$, а точек $n$ порядка $10^5$ и хочется их «засунуть в дошку» (массив): отсортировать, выкинуть одинаковые и присвоить каждой значение от $0$ до (количество − $1$). Функция unique удаляет дубликаты (подряд идущие равные элементы), поэтому для всего массива сначала надо отсортировать.
57:07 Что она делает: уникальные значения переставляет в начало (в отсортированном порядке), дубликаты оказываются в конце, а возвращает итератор на конец уникальной части. Использовать так:
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end()); // осталась только уникальная частьsort и unique уникальные значения идут в начале, erase удаляет хвост.58:46 Из чата подсказали более короткий вариант без resize: erase стирает подотрезок вектора, то есть тот конец, который нас не интересует (так и записано выше). 59:21 unique работает за $O(n)$ (простой проход: если элемент равен предыдущему, он игнорируется), поэтому быстрее set, который работает за $O(n\log n)$. 59:44 Зачем это, если можно обойтись одним циклом for без сортировки: потому что часто это придётся делать, и каждый раз писать цикл, создавать новый вектор и копировать в него надоедает; к двум строчкам привыкаешь, и этого достаточно.
После сжатия номер значения $x$ находят бинарным поиском: lower_bound(v.begin(), v.end(), x) - v.begin().
lower_bound и upper_bound 60:1860:20 lower_bound(begin, end, x) возвращает итератор на первый элемент $\ge x$, upper_bound — на первый элемент $>x$. 60:51 Нужно следить, что результат может оказаться v.end(), если подходящего элемента нет — тогда разыменовывать его нельзя (иначе ошибка).
61:09 lower_bound — общая функция, принимающая итераторы от любых контейнеров, и она ничего не знает про устройство контейнера. Поэтому для set нужно использовать метод s.lower_bound(x): он реализован с учётом того, что set — двоичное дерево поиска, и спускается по дереву за $O(\log n)$.
setset как $O(\log^2 n)$. На самом деле у итераторов set нет произвольного доступа: чтобы «прыгнуть» к середине, итератор нужно двигать шаг за шагом, и общий std::lower_bound делает порядка $O(n)$ шагов итератора (хотя сравнений всего $O(\log n)$). Замер (g++, 200 000 элементов, 2000 запросов): метод s.lower_bound(x) — около $1{,}5$ мс, общая функция — около $4{,}4$ секунды. Вывод тот же, но куда жёстче: для set и map всегда вызывайте метод контейнера.63:24 Пусть первая подгруппа задачи — $n$ до $10$, и нужно перебрать все перестановки и что-то на них посчитать. Заводим вектор p размера $n$, заполняем iota-ом числами от $0$ до $n-1$ (минимальная перестановка), а дальше:
vector<int> p(n);
iota(p.begin(), p.end(), 0);
do {
// работаем с перестановкой p
} while (next_permutation(p.begin(), p.end()));64:11 next_permutation принимает два итератора и превращает подотрезок в следующую перестановку в лексикографическом порядке (выписать все перестановки, отсортировать лексикографически, найти текущую и взять следующую). Возвращает false, когда перестановки кончились. 64:44 Есть и prev_permutation (преподаватель им никогда не пользовалась).
64:56 Возвращаясь к lower_bound: общая функция «lower_bound(s.begin(), s.end(), x)» пишет обычный бинпоиск, на каждой итерации которого обращается к «середине» множества, а у set такое обращение стоит не $O(1)$; метод же set знает, что это дерево поиска, и делает спуск. Про это важно помнить.
pb_ds 65:4166:03 Есть библиотека pb_ds (policy based data structures) — расширение GNU. Она подключается отдельными заголовками (в bits/stdc++.h она не входит), и нужно прописать using namespace __gnu_pbds;.
66:47 ordered_set. Обычный set не умеет работать с индексами элементов: можно добавлять, удалять, делать lower_bound, но нельзя спросить «какой элемент по порядку» и «какой у элемента номер». ordered_set — это set, в котором можно пользоваться индексами. Задаётся «магической» строкой из пяти строчек, которую обычно просто заучивают или кладут в шаблон.
68:04 Преподаватель подчёркивает: эта штука очень медленная (заметно медленнее set), и никто не делает задач, в которых её обязательно использовать — если вы придумали решение с ней, скорее всего, можно обойтись без неё (например, деревом Фенвика или другим способом).
Интерфейс как у обычного set (insert и т. д.) плюс: 68:21 find_by_order(i) — по индексу выдаёт элемент; 68:37 order_of_key(x) — по значению выдаёт индекс (сколько элементов строго меньше $x$).
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set os;
for (int x : {50, 10, 30, 20, 40}) os.insert(x);
cout << *os.find_by_order(2) << "\n"; // элемент с индексом 2 (с нуля) в отсортированном порядке: 30
cout << os.order_of_key(35) << "\n"; // сколько элементов строго меньше 35: 3
gp_hash_table<int, int> h; // хеш-таблица с открытой адресацией
h[5] = 7;
cc_hash_table<int, int> h2; // хеш-таблица с цепочками
h2[5] = 1;69:01 «Спойлер: вам это, скорее всего, не пригодится».
69:32 Там же лежат две хэш-таблицы (про них рассказывали на прошлой лекции): gp_hash_table — «мапа» с открытой адресацией, работает быстрее, и cc_hash_table — с цепочками (закрытая адресация), реализована тоже быстрее обычной. Используются как обычная map: тип ключа, тип значения, обращение h[x]. Эти библиотеки в bits не входят — их надо подключать отдельно.
70:26 Лямбда-функции — «прямо очень удобно и полезно». Они позволяют хранить функцию как объект и под каждый DFS (из десяти разных видов, которые нужно сделать) или под каждый компаратор сортировки не заводить отдельную глобальную функцию, а использовать её там, где нужно.
71:03 Допустим, нужно отсортировать вектор пар. Обычный sort вызывает оператор «меньше», определённый для pair: он сначала сравнивает первые элементы, если они равны — вторые. Если нужно отсортировать только по первым и вторым не различать, то в sort третьим аргументом передают компаратор — функцию, принимающую два элемента $a$ и $b$ (такие, как лежат в векторе) и возвращающую true, если $a$ строго меньше $b$, и false иначе.
true именно для строго меньше. Если вернуть «меньше либо равно», то sort не сможет правильно упорядочить элементы: с каким-то шансом он отработает правильно, но с большим шансом выдаст неправильный результат (а то и упадёт). Про это очень важно помнить.72:45 Компаратор можно написать как обычную глобальную функцию (return a.first < b.first;) и передать как аргумент. Но под каждую сортировку писать её неудобно, поэтому обычно пишут лямбду:
sort(v.begin(), v.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
return a.first < b.first; // строго меньше
});73:26 Лямбда начинается с квадратных скобок, дальше в круглых — аргументы (как у обычной функции), в фигурных — тело. У этой функции нет имени, она хранится как объект и исчезает после того, как sort завершится.
74:02 Обычные функции «видят» только свои аргументы и глобальные переменные. Если нужно, чтобы функция видела то, что есть в окружающей области (скажем, переменную x, которую нельзя передать аргументом, потому что аргументов должно быть ровно два), в квадратных скобках пишут & — тогда лямбда получает доступ ко всем переменным, существующим там, где её создали. 75:19 Тип возвращаемого значения чаще всего компилятор восстанавливает сам; если нужно задать его вручную, пишут стрелочку: [&](int a, int b) -> bool { … }.
76:32 Второй сценарий — сложная задача на дереве или графе, где нужно десять разных DFS (один считает компоненты связности, другой размеры, третий ещё что-то). Не хочется писать десять функций и передавать в каждую граф и массивы — вместо этого лямбду сохраняют в переменную: auto dfs = [&](...) {...};.
77:42 Проблема: когда лямбда объявляется так, внутри себя она ещё не знает, что у неё будет имя dfs: сначала создаётся объект, потом он записывается в переменную. Поэтому, чтобы сделать рекурсию, нужно передать функцию в саму себя: первым параметром идёт self, вызываем self(self, u), а снаружи dfs(dfs, v). 78:44 И обязательно нужно указать тип возвращаемого значения (-> void или -> int и т. д.): для рекурсивной функции компилятор не может догадаться о нём сам и будет ругаться.
// компаратор: только по первому полю, строго «меньше»
sort(v.begin(), v.end(), [](const pair<int,int>& a, const pair<int,int>& b) {
return a.first < b.first;
});
// захват переменных окружения
int x = 10;
auto addx = [&](int y) { return x + y; }; // addx(5) == 15
// рекурсивная лямбда: первым параметром передаём «саму себя», тип результата указываем явно
vector<vector<int>> g(n);
vector<int> sz(n, 1);
auto dfs = [&](auto self, int v) -> void {
for (int u : g[v]) {
self(self, u);
sz[v] += sz[u];
}
};
dfs(dfs, 0);79:12 Почему пишем auto, а не сразу void? auto — это тип переменной, в которой хранится функция (на самом деле что-то вроде function<…>; знать его не нужно). А -> void — это тип, который возвращает функция. 81:09 И self нужен потому, что, пока считается выражение справа от «=», объект создаётся «без имени» и не знает, что будет называться dfs; он знает только, что у него есть аргумент self, который можно вызвать.
81:35 Зачем лямбды, если можно вынести функцию? Чтобы писать их прямо в sort, не захламлять код, писать маленькие DFS и не выносить граф в глобальные переменные или аргументы.
range-based for и structured bindings 82:5483:05 Range-based for — это тот for, который знаком по Питону (там он единственный). Работает с любым итерируемым контейнером, у которого есть begin и end:
for (int x : v) cout << x << " "; // x — копия очередного элемента
for (int& x : v) x *= 2; // ссылка — меняем сам элемент83:49 Компилятор разворачивает его в обычный цикл по итераторам: for (auto it = v.begin(); it != v.end(); ++it) { int x = *it; … }. 84:20 Удобно, когда не нужен индекс, и незаменимо для контейнеров без доступа по индексу — например, set: перебрать все элементы можно for (int x : s) — иначе не написать. Перебор set целиком работает за его размер — потому что идёт «обход дерева в глубину».
84:59 Structured bindings (C++17): когда есть пара, можно «распаковать» её в две отдельные переменные: auto [x, y] = pr; — создаются новые переменные x, y, и в них копируются first и second. Это комбинируется с range-based for: если у вас vector<pair<int,int>>, хранящий рёбра графа («куда идём» и вес), то их перебирают так:
for (auto [to, w] : g[v]) { /* to — вершина, w — вес */ }vector<int> v = {1, 2, 3};
for (int x : v) cout << x << " "; // x — копия элемента
for (int& x : v) x *= 2; // ссылка: меняем сам элемент
set<int> s = {5, 1, 3};
for (int x : s) cout << x << " "; // 1 3 5 — без индексов и итераторов
pair<int,int> pr = {1, 2};
auto [a, b] = pr; // structured bindings (C++17): a = 1, b = 2
vector<pair<int,int>> edges = {{2, 10}, {3, 20}}; // (куда, вес)
for (auto [to, w] : edges) cout << to << "/" << w << " ";86:12 Вопрос: сколько стоит такой перебор у set? За длину контейнера. 86:28 Если перебирать set методом «find/lower_bound от каждого элемента» (а не обходом), получится $O(n\log n)$, а for по элементам set — $O(n)$.
87:21 Вопрос из зала («почему у меня компилятор не принимает auto [a, b] = pair?»): преподаватель не знает, возможно, версия стандарта у студента старая — structured bindings появились в C++17.
88:05 Директивы препроцессора — строки, которые начинаются с решётки #. Они позволяют до этапа компиляции что-то сделать с кодом: препроцессор преобразует код программы так, чтобы получить код, который уже понимает компилятор, и отдаёт его ему.
#define: макросы 88:5788:57 #define задаёт макросы — спорную, но удобную вещь: они дают «шорткаты», позволяя заворачивать выражения и писать их в более коротком виде. Самый удобный, который советуют всегда использовать:
#define all(v) (v).begin(), (v).end()
sort(all(v)); // sort((v).begin(), (v).end());89:32 Препроцессор не «считает что-то умное», а просто заменяет текст везде, где увидит all(v). Поэтому в макросах нужно ставить скобки вокруг аргументов: если написать #define prod(a, b) a * b и вызвать prod(1 + 2, 3), получится 1 + 2 * 3, и приоритет операций сломается; со скобками ((a) * (b)) всё работает. 91:00 Аналогично можно сделать rall (rbegin/rend) и свои сокращения — «обычно хватает только all».
#define int long long#define int long long заменит любое слово int на long long, в том числе в int main() — получится long long main(), и программа не скомпилируется. Поэтому при таком макросе пишут signed main() (или int32_t main()). Преподаватель оценивает это как «очень плохо», делать так не надо: рано или поздно упрётесь в странности; использовать нужно с большой осторожностью.92:26 Ещё можно написать просто #define NAME (пустое определение). Это не макрос, который что-то делает: вы лишь сообщаете препроцессору, что метка NAME существует.
LOCAL и отладочный режим STL 92:4992:52 Есть метка _GLIBCXX_DEBUG: она говорит компилятору (GCC), что мы хотим компилироваться с повышенным уровнем отладки. Если написать эту метку до подключения библиотек, то в библиотеках сработают дополнительные проверки: препроцессор при #include просто подставляет код библиотеки целиком, а там написано много #ifdef — «если есть метка, делаем дополнительные проверки».
93:56 Пример: vector<int> a(5); int i = 7; cout << a[i]; — без метки это неопределённое поведение (undefined behavior): может сработать, прочитав какой-то мусор, а может упасть с RE (segmentation fault) — и вы не поймёте, где вышли за границу. С _GLIBCXX_DEBUG контейнер компилируется в другом режиме и в operator[] проверяет индекс; при выходе за границу программа остановится с понятным сообщением (проверено запуском):
Error: attempt to subscript container with out-of-bounds index 7, but
container only holds 5 elements.95:19 Ошибка находится со 100 % вероятностью — она не может «проскочить незамеченной». Подвох — все эти проверки занимают много времени: код под _GLIBCXX_DEBUG работает в разы медленнее, поэтому посылать в тестирующую систему с этой меткой не стоит; слать её нужно только локально, когда вы хотите проверить, есть ли в программе баг.
96:00 Чтобы не забывать включать и выключать отладочный режим, есть директива #ifdef — условный if: он проверяет, существует ли метка (макрос) с таким именем; если на этом месте где-то раньше был #define LOCAL, то код внутри выполнится, если нет — препроцессор просто пропустит эту секцию. Закрывается через #endif; есть также #ifndef («если такого определения нет») и #else.
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>96:30 Но метка LOCAL должна быть только у нас, а в тестирующей системе её быть не должно: тогда при отправке #define просто не сработает. 97:36 Чтобы она была локально, в CLion можно добавить определение -DLOCAL в настройки (CMakeLists.txt) — тогда компилятор при каждой сборке добавит в самое начало #define LOCAL. Если компилируете через терминал: g++ main.cpp -DLOCAL (-D просто добавляет определение; имя можно любое). Это очень удобно: вы вставляете в шаблон такую конструкцию, и локально всё работает под отладкой, а в тестирующей системе — всегда без неё. 100:03 И метку всегда нужно писать до подключения библиотек, иначе они скомпилируются в обычном режиме.
#pragma 100:13100:17 #pragma — указание компилятору, как оптимизировать программу. Бывает два вида: #pragma GCC optimize(...) (какие оптимизации использовать) и #pragma GCC target(...) (под какие архитектуры собирать).
-O0 (без оптимизаций), -O1, -O2, -O3. Стандартный — -O2 (достаточно сильно оптимизирует, но безопасно). -O3 — самый высокий уровень; он может приводить к плохим последствиям, в промышленности его обычно не используют, но он реально ускоряет код. Включается так: #pragma GCC optimize("O3").unroll-loops: цикл с небольшим числом итераций «разворачивается» в подряд записанные команды, и без прыжков по циклу работает быстрее. Остальные — «казино»: правил нет, и часто это не помогает.target самое полезное — avx2: у современных процессоров есть инструкции, работающие сразу с крупными блоками данных; если, например, ко всем числам массива прибавить константу, то обычный процессор прибавляет по одному числу, а такая инструкция — сразу пачками, в несколько раз быстрее. Но на тестирующих машинах они есть не везде, и компилятор не всегда использует их — «напишите и поверьте, что повезёт».int сразу); 512 бит — у расширения AVX-512, которое поддерживается ещё реже. Если машина тестирования не поддерживает указанную архитектуру, программа может упасть с ошибкой выполнения.103:49 Важный момент про -O3: -O2 — «нормальный» уровень, при котором понятно, что происходит в машинном коде. -O3 — жёсткий: компилятор может выкинуть кусок кода или переупорядочить его. Если запустить встроенный отладчик, то вы идёте подряд по строчкам, а он вдруг прыгает на десять вниз или вверх, в рандомную функцию или пропускает строчку — строчки программы не соответствуют строчкам машинного кода. Дебажить в таком режиме невозможно, но и не нужно: дебажить вы будете локально на маленьких примерах.
105:12 Есть ещё -Ofast и опция -ffast-math: они оптимизируют вычисления с плавающей точкой, из-за чего может возникнуть очень большая погрешность, и задача не пройдёт по точности, хотя должна. Преподаватель не советует в это глубоко лезть: на реальных олимпиадах это, скорее всего, никогда не поможет.
106:43 Полезный приём: задача требует ввода-вывода через файлы, а вы хотите отлаживаться в консоли. Тогда в начале программы пишут:
#ifndef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endifТогда не локально потоки идут через файлы, а локально всё работает через обычные cin / cout.
108:04 У генератора случайных чисел есть seed («семечка») — число, которое задаёт, какая будет последовательность. Это не первое число последовательности, а задающее её значение: при одинаковом seed последовательность всегда одна и та же. Поэтому обычно берут текущее время: между запусками программы пройдёт хотя бы миллисекунда, и seed будет каждый раз разный. 108:46 Время берут так: chrono::steady_clock::now().time_since_epoch().count() — объект, задающий текущее время, переводят в количество времени с начала эпохи и берут число.
109:42 Если seed нужен постоянный (чтобы всё воспроизводилось), в скобках просто пишут число.
110:03 Генератор mt19937 — объект с оператором «круглые скобки»: rng() возвращает случайное число (mt19937_64 — 64-битный вариант). 110:43 Чтобы получить число из диапазона $[l,r]$, берут остаток по модулю: l + rng() % (r - l + 1).
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // seed — текущее время
int rnd(int l, int r) { return l + rng() % (r - l + 1); } // случайное число из [l, r]
vector<int> v(10);
iota(v.begin(), v.end(), 0);
shuffle(v.begin(), v.end(), rng); // случайная перестановка111:18 Где нужен рандом. Например, чтобы перемешивать массивы — это очень полезно, если вы хотите «запихать» решение, которое, скорее всего, работает на данных, расположенных в случайном порядке: shuffle(v.begin(), v.end(), rng) перемешивает отрезок контейнера случайным образом, используя в качестве внутреннего генератора то, что вы передали.
112:40 Санитайзеры — штука, которая умеет отлавливать «неопределённое поведение» (UB) в C++ и сообщать о нём. Это флаг компиляции: g++ main.cpp -fsanitize=address,undefined.
address отлавливает выход за границы массива. Разница с _GLIBCXX_DEBUG: тот умеет ловить выход за границы вектора, но если вы пишете int a[5], он не поможет, а address-санитайзер превращает UB в гарантированную ошибку с осмысленной информацией.undefined сообщает о других неопределённых поведениях: переполнение знаковых чисел, деление на ноль, некорректный сдвиг (например, на $100000$), разыменование нулевого указателя.114:43 Важный момент: санитайзеры работают только на Linux и macOS. Как добавить их в CLion, преподаватель не помнит (тот же флаг нужно прописать в настройках сборки). 115:16 И, естественно, они сильно замедляют программу — это нужно помнить.
115:34 «Самое полезное». Стресс-тесты нужны всегда и везде — на всех олимпиадах, турах, на Codeforces. Это самый важный инструмент, который должен быть с самого начала тура, и нужно быть на $100\%$ уверенным, что вы понимаете, как его делать правильно.
116:03 Есть два варианта: писать стресс-тест в одном файле или в нескольких. Преподаватель делает в нескольких — ей так намного удобнее: если вы уже написали большую программу с кучей глобальных переменных, а потом захотели «постресить», то всё придётся переделывать. Набор файлов:
solution.cpp — ваше решение (читает из stdin, пишет в stdout);stupid.cpp — «тупняк»: долгое, но гарантированно верное решение;gen.cpp — генератор нужных вам тестов (выводит тест в stdout в нужном формате);stress.py — скрипт, который гоняет эти программы по кругу и ищет тест, на котором решения расходятся.diff.117:46 Устройство stress.py. Библиотека os позволяет взаимодействовать с системой, в том числе вызывать команды командной строки (os.system возвращает код возврата команды). Сначала компилируем три программы — вызываем g++, передаём имя файла и -o имя результата; буква f перед строкой в Python делает строку форматированной — в фигурные скобки можно подставлять переменные. Потом — бесконечный while, который крутится, пока не найдёт тест, номер теста сохраняется для удобства.
119:31 Перенаправление ввода-вывода в командной строке работает через «меньше» и «больше»: ./solution < in.txt — вместо ввода с клавиатуры программа получает содержимое файла; ./solution > out.txt — вывод программы идёт в файл. Благодаря этому мы запускаем генератор и пишем его вывод в in.txt; затем решение — на вход ему даём in.txt, а вывод пишем в out.txt; затем верное решение — вывод в ans.txt; и сравниваем файлы: на Linux/macOS утилитой diff, на Windows — fc (от file compare). Она возвращает $0$, если файлы совпадают, и не $0$, если отличаются.
121:42 Код возврата — число, которое говорит, как отработала программа: по договорённости $0$ — «всё хорошо», не $0$ — «что-то пошло не так». Если генератор вернул не $0$ — ошибка выполнения в генераторе; решение вернуло не $0$ — runtime error; diff/fc вернула не $0$ — найден тест, на котором выводы отличаются, скрипт останавливается; когда он нашёл тест, в in.txt лежит вход, в out.txt — вывод вашей программы, в ans.txt — правильный. 123:19 В конце команды > /dev/null (на Windows > nul) нужен, чтобы служебный вывод diff нам не мешал: /dev/null — «системная корзина», всё, что туда приходит, стирается.
Ниже — рабочий вариант скрипта и примера (проверен запуском: на нём баг в «быстром» решении находится за $10$ тестов).
import os, sys
def run(cmd):
return os.system(cmd)
# компилируем три программы
for name in ("gen", "solution", "stupid"):
if run(f"g++ -std=c++17 -O2 {name}.cpp -o {name}") != 0:
print("compilation error:", name)
sys.exit(1)
t = 0
while True:
t += 1
if run(f"./gen {t} > in.txt") != 0: # генератор упал
print("generator runtime error"); break
if run("./solution < in.txt > out.txt") != 0: # решение упало (код возврата != 0)
print("solution runtime error on test", t); break
if run("./stupid < in.txt > ans.txt") != 0:
print("stupid runtime error on test", t); break
if run("diff out.txt ans.txt > /dev/null") != 0: # на Windows: fc out.txt ans.txt > nul
print("WRONG ANSWER on test", t)
break
if t % 100 == 0:
print("ok", t)Генератор получает номер теста как argv[1] и использует его как seed (mt19937 rng(atoi(argv[1]))) — это отличие от лекционного варианта (там seed берётся по времени): любой тест воспроизводится, и два подряд идущих запуска не дают одинаковых тестов. Тесты нужно делать маленькими ($n\le6$): баг проще найти и разобрать.
125:15 Если ответ неоднозначен (несколько верных), нужен чекер — программа, которой дают тест и ответ, а она сама проверяет его корректность; писать его неприятно, но схема та же. 126:50 Обычно перед пятичасовым туром, если есть пробный, шаблон готовят заранее, а если нет — то в начале тура за три минуты его пишут. Потом можно спокойно не «ловить багу глазами в 200 строках», а запускать стресс. 127:45 «Как бы стрессы нужны всегда. Без них контест пройдёт гарантированно хуже.»
128:07 Есть консольный отладчик gdb: он сложный, в консоли показывает инструкцию, на которой вы находитесь, и там можно ставить точки останова; пользоваться им больно, преподаватель им не пользуется. Про отладчики других сред она сказать не может. 129:22 В CLion отладчик очень удобный: нажимаете кнопку «Debug», ставите точки останова (breakpoints) — и всё работает.
x + 10), и оно посчитается в реальном времени.131:38 Для задач с открытыми тестами, где вы долго считаете что-то локально, в CLion есть конфигурации: по умолчанию — Debug; можно создать Release — он не включает отладочные штуки, и программа работает сильно быстрее. Если пару часов что-то локально читаете — запускайте под Release или компилируйте руками из терминала. 132:28 Иногда при запуске через отладчик «кидает» в файл с ассемблерным кодом — обычно из-за нетривиального аварийного завершения; если отладчик может обработать ошибку, он просто покажет строку, где она случилась. Отладка интерактивных задач — отдельная тема, универсального способа нет, можно отлаживаться выводом или «глазками».
134:19 После перерыва — разбор контестов по строкам (префикс-функция, Z-функция, бор). Остановились на задаче «сколько строк меньше».
134:41 Даны слова $t_1,\dots,t_n$ и изменяемая строка $S$. Приходят запросы вида $(k, c)$: в строке $S$ с позиции $k$ и до конца нужно сделать суффикс, равный символу $c$ (весь суффикс заменяется буквой $c$). В самом начале и после каждого такого запроса нужно сказать, сколько слов $t_i$ лексикографически меньше $S$. Суммарная длина слов — до миллиона, хочется что-то около линейного.
136:10 Сначала без изменений. Первое, что приходит на ум — бор. В вершине храним term (сколько слов заканчивается в ней) и cnt (сколько терминальных вершин достижимо из неё, считая по бору вниз). 137:15 Идём по бору по строке $S$. Слово $t$ меньше $S$, если у них совпадает какой-то префикс, а первый несовпадающий символ у $t$ меньше (или $t$ — собственный префикс $S$). Значит, на каждом шаге нужно прибавить все слова, которые идут по первой букве меньше, чем наша — то есть всех детей текущей вершины с буквами меньше $S_i$ (по префиксным суммам считается быстро) — и затем сдвинуться по букве $S_i$ и повторить.
139:30 Что делать с запросами. Ключевой момент: меняется суффикс, причём на вполне конкретную вещь — на повторение одной буквы $c$. Определим $B(v,c)$ — «вклад» вершины $v$, если $S$ идёт из неё по символу $c$: это $\mathrm{term}(v)$ плюс сумма $\mathrm{cnt}$ по детям с буквой меньше $c$ (просто префиксные суммы для одного шага). Путь строки $S$ по бору при изменении суффикса перестраивается так: префикс остаётся тем же, а дальше мы идём по бору чисто по символам $c$. 141:35 Такие пути удобно хранить стеком из «переходов» $(v, \text{cnt}, c)$ — «из вершины $v$ идём $\text{cnt}$ шагов по рёбрам $c$». Запрос удаляет с верхушки стека префикс (верхний кусочек — меняется ведь только хвост) и заменяет его новым переходом.
143:29 Осталось быстро считать вклад одного такого перехода. Разобьём бор на $c$-цепочки: для фиксированной буквы $c$ из каждой вершины можно идти по $c$-ребру вниз — это пути «по символу $c$»; каждая вершина принадлежит какой-то $c$-цепочке. Тогда $(v,\text{cnt},c)$ — это подотрезок $c$-цепочки, начинающийся в $v$. 145:48 Для каждой цепочки считаем префиксные суммы величин $B(\cdot,c)$; сумма по подотрезку — разность двух префиксных сумм. Поэтому удаление такого подотрезка — это нахождение его цепочки и удаление, а добавление нового — переход в нужную цепочку и взятие оттуда $\text{cnt}$ вершин. 147:16 Всего $26$ букв, и каждое ребро бора входит в цепочки; в итоге суммарно получается порядка $26N$ (плюс $N$ на сами рёбра), и каждый запрос сводится к нескольким операциям со стеком.
148:41 Дана перестановка $P_1,\dots,P_n$ и шаблон (массив) $H_1,\dots,H_k$. Нужно посчитать количество подотрезков перестановки длины $k$, которые после «сжатия» (замены каждого значения на его номер в отсортированном подотрезке — то есть с сохранением относительного порядка) совпадают с таким же образом сжатым шаблоном. Каждому числу присваивается то место, на котором оно оказалось бы при сортировке: важен именно относительный порядок элементов. (Собственный пример: подотрезок $5\,3\,1\,7$ после такого сжатия превращается в $3\,2\,1\,4$ — и такое же сжатие должно получиться у шаблона.) Это «красивая и не очень сложная» задача.
150:22 На вопрос, что в исходных данных стоит не сама перестановка, а индексы минимального, второго минимального и так далее: это обратная перестановка, и задачи эквивалентны: если взять $R[P_i]=i$, то задача сводится к описанной.
151:44 Идея: префикс-функция с «порядковым» равенством. Вспомним, как работает обычная префикс-функция: к текущему префиксу добавляют символ и проверяют равенство. Определим новое равенство строк: две последовательности равны, если у них одинаковый относительный порядок ($S_i>S_j\iff S'_i>S'_j$). Для обычной префикс-функции нужно было сравнивать символы; теперь нужно проверять, что новый добавленный элемент имеет правильное отношение порядка ко всем предыдущим. 155:22 На самом деле достаточно посмотреть на два элемента: ближайший по значению меньший и ближайший по значению больший среди ранее добавленных, и проверить, что новый элемент лежит между ними так же, как в шаблоне. Если эти две проверки выполнены, то порядок сохраняется. Нужные соседи в шаблоне вычисляются заранее: можно хранить set и делать lower_bound, а можно удалять элементы из двусвязного списка, отсортированного по значению, идя от конца к началу (так «соседями» окажутся именно ближайшие значения среди более ранних элементов).
// Order-preserving KMP: ищем окна длины m в перестановке t, у которых относительный порядок элементов такой же, как у p.
// Значения в p (и в t) различны.
struct OrderMatcher {
int m;
vector<int> lo, hi; // lo[i] — позиция ближайшего по значению МЕНЬШЕГО среди p[0..i-1], hi[i] — БОЛЬШЕГО (или -1)
vector<int> pi;
template <class V> bool ok(const V& a, int start, int i) const { // можно ли дописать a[start + i] к совпавшему префиксу длины i
int x = a[start + i];
return (lo[i] < 0 || a[start + lo[i]] < x) && (hi[i] < 0 || a[start + hi[i]] > x);
}
OrderMatcher(const vector<int>& p) : m(p.size()), lo(m, -1), hi(m, -1), pi(m, 0) {
// для каждой позиции ищем соседей по значению среди более ранних: удаляем позиции из отсортированного списка с конца
vector<int> idx(m), prv(m), nxt(m), where(m);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int a, int b) { return p[a] < p[b]; });
for (int r = 0; r < m; r++) { where[idx[r]] = r; prv[r] = r - 1; nxt[r] = r + 1; }
for (int i = m - 1; i >= 0; i--) {
int r = where[i];
lo[i] = prv[r] >= 0 ? idx[prv[r]] : -1;
hi[i] = nxt[r] < m ? idx[nxt[r]] : -1;
if (prv[r] >= 0) nxt[prv[r]] = nxt[r];
if (nxt[r] < m) prv[nxt[r]] = prv[r];
}
for (int i = 1, k = 0; i < m; i++) { // обычная префикс-функция, но сравнение — «порядковое»
while (k > 0 && !ok(p, i - k, k)) k = pi[k - 1];
if (ok(p, i - k, k)) k++;
pi[i] = k;
}
}
vector<int> find(const vector<int>& t) const { // начала всех подходящих окон
vector<int> res;
for (int i = 0, k = 0; i < (int)t.size(); i++) {
while (k > 0 && (k == m || !ok(t, i - k, k))) k = pi[k - 1];
if (ok(t, i - k, k)) k++;
if (k == m) res.push_back(i - m + 1);
}
return res;
}
};160:38 На вопрос, нельзя ли использовать «ближайший больший слева, меньший справа» с помощью стека — это не совсем то: ближайшего по значению среди предыдущих нужно искать не как «ближайший слева в массиве», а по значениям в префиксе.
162:36 Даны два текста: шаблон $t$ и огромная строка $s$ (длина до $\sim 6\cdot10^7$), ограничение по памяти — около $200$ МБ. Нужно подсчитать вхождения шаблона в строку. 163:10 Хранить всю строку целиком нельзя.
165:29 Вспомним, как считается префикс-функция по строке $t\,\#\,s$: на каждом шаге мы смотрим на значение на предыдущей позиции, пока символы не совпадут — каждый раз «шагаем» по префикс-функции, а при совпадении увеличиваем текущее значение. 165:34 Заметим, что в такой строке значение префикс-функции никогда не больше $|t|$ (из-за разделителя). Значит, хранить префикс-функцию на всём длинном тексте не нужно: нужны только префикс-функция шаблона и предыдущее значение для текста — больше ничего. И саму строку $s$ тоже хранить не нужно: можно считывать её по одному символу (char c; cin >> c или get). 166:19 Это «прикольный хак»: строку считывать не надо, ничего особо хранить не надо.
// Считаем вхождения шаблона t в огромный текст, читая текст по одному символу и не храня его
long long countOccurrences(const string& t, istream& in) {
int m = t.size();
vector<int> pi = prefixFunction(t); // префикс-функция только шаблона
long long cnt = 0;
int q = 0; // длина текущего совпадения (= значение префикс-функции на текущем символе)
char c;
while (in.get(c)) {
while (q > 0 && (q == m || t[q] != c)) q = pi[q - 1];
if (t[q] == c) q++;
if (q == m) cnt++; // нашли вхождение
}
return cnt;
}166:48 Ещё один приём, чтобы упростить цикл: заранее посчитать массив переходов go[i][c] — значение префикс-функции, в которое мы придём из префикса длины $i$ по символу $c$ (автомат). Тогда внутренний while отпадает, и новый символ сразу переводит нас в следующее состояние. 169:32 Если в этот момент значение стало равным $|t|$ — нашли вхождение.
170:49 Дана Z-функция строки; нужно построить её префикс-функцию. 171:18 Пусть $z_i=L$: значит, префикс длины $L$ совпадает с подстрокой, которая начинается в позиции $i$. Тогда для любого $t\in[0,L)$ префикс-функция в позиции $i+t$ не меньше $L-t$ — «блок» $[i,i+L)$ является суффиксом префикса соответствующей длины. 173:12 Но присваивать $\pi_{i+t}=\max(\pi_{i+t},\,L-t)$ для всех $t$ — слишком долго. Делаем так: сначала на конце каждого блока ставим pi[i+z[i]-1] = max(.., z[i]), а затем проходим справа налево и обновляем pi[i-1] = max(pi[i-1], pi[i] - 1): значение «шагает» влево, уменьшаясь на единицу — это ровно то, что нужно. 175:58 Доказывается от противного: если бы в какой-то позиции значение префикс-функции строго больше всех $z$-вкладов, то, шагнув по ней, мы получили бы $z$-блок, который есть в исходных данных, — противоречие.
177:31 Теперь обратная задача. Сделаем строку с заданной префикс-функцией, а по ней посчитаем Z-функцию — её считать уже умеем. 179:22 Строим: $A_0$ — новая «буква». Если $\pi_i>0$, то $A_i=A_{\pi_i-1}$ (суффикс префикса должен совпасть с префиксом: достаточно посмотреть на элемент, который надо «перенести назад»). Если $\pi_i=0$, то берём совершенно новую «букву» — глобальный счётчик числа различных символов. Затем запускаем Z-функцию. 180:46 Нужно аккуратно: по префикс-функции строку однозначно восстановить нельзя (например, «abc» и «abd» имеют одну и ту же префикс-функцию $[0,0,0]$); но Z-функция у любой такой строки одна и та же, поэтому наш результат верен.
vector<int> prefixFunction(const string& s) {
int n = s.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) {
int k = pi[i - 1];
while (k > 0 && s[i] != s[k]) k = pi[k - 1];
if (s[i] == s[k]) k++;
pi[i] = k;
}
return pi;
}
vector<int> zFunction(const string& s) { // z[0] считаем равным 0
int n = s.size();
vector<int> z(n, 0);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
if (i + z[i] > r) l = i, r = i + z[i];
}
return z;
}
// Z-функция -> префикс-функция
vector<int> prefixFromZ(const vector<int>& z) {
int n = z.size();
vector<int> pi(n, 0);
for (int i = 1; i < n; i++) // z-блок [i, i + z[i]) даёт на своём конце значение z[i]
if (z[i] > 0) pi[i + z[i] - 1] = max(pi[i + z[i] - 1], z[i]);
for (int i = n - 1; i > 0; i--) // идём справа налево: слева значение не меньше «правое − 1»
pi[i - 1] = max(pi[i - 1], pi[i] - 1);
return pi;
}
// префикс-функция -> Z-функция: строим любую строку с такой префикс-функцией и считаем по ней Z
vector<int> zFromPrefix(const vector<int>& pi) {
int n = pi.size(), fresh = 0;
vector<int> a(n);
a[0] = fresh++;
for (int i = 1; i < n; i++)
a[i] = pi[i] > 0 ? a[pi[i] - 1] : fresh++; // pi = 0 — берём совершенно новую «букву»
// Z-функция по массиву чисел (алфавит большой, поэтому строкой не обойтись)
vector<int> z(n, 0);
for (int i = 1, l = 0, r = 0; i < n; i++) {
if (i < r) z[i] = min(r - i, z[i - l]);
while (i + z[i] < n && a[z[i]] == a[i + z[i]]) z[i]++;
if (i + z[i] > r) l = i, r = i + z[i];
}
return z;
}182:21 Дана строка; нужно уметь сравнивать между собой две её подстроки на равенство. Это «философски просто хэши»: берём хэш подстроки.
183:15 Есть два вида полиномиального хэша. «Прямой»: $\sum s_i P^{\,i}$, и «обратный»: $\sum s_i P^{\,|s|-i}$ (старший символ — со старшей степенью). Преподаватель советует никогда не пользоваться прямым — он «очень плохой, непонятный», приходится всё время домножать на степень и всё запутывается. 184:12 Обратный хэш считается проще: $h_{i+1}=h_i\cdot P+s_i$ (предыдущий умножаем на основание и добавляем новый символ). И хэш подстроки $[l,r)$ считается без цикла: $H(l,r)=h_r-h_l\cdot P^{\,r-l}$ — «буквально ноль строк».
186:25 Математика. Хэш подстроки $s[l..r)$ равен $\sum_{i=l}^{r-1}s_i P^{\,r-1-i}$. В префиксном хэше $h_r$ слагаемое $s_i$ (при $i<r$) стоит с множителем $P^{\,r-1-i}$, поэтому $h_r=\sum_{i<r}s_iP^{\,r-1-i}$. Вклад первых $l$ символов в $h_r$ — это $\sum_{i<l}s_iP^{\,r-1-i}=P^{\,r-l}\sum_{i<l}s_iP^{\,l-1-i}=P^{\,r-l}\cdot h_l$. Вычитая его, получаем в точности $\sum_{i=l}^{r-1}s_iP^{\,r-1-i}$. Сила обратного хэша: «хвостик», оставшийся от префикса, отличается ровно на степень $P^{\,r-l}$.
typedef unsigned long long ull;
const ull MOD = (1ULL << 61) - 1;
ull mulmod(ull a, ull b) { __uint128_t t = (__uint128_t)a * b; ull r = (ull)(t & MOD) + (ull)(t >> 61); return r >= MOD ? r - MOD : r; }
struct StringHash { // «обратный» полиномиальный хэш: h[i+1] = h[i] * P + s[i]
vector<ull> h, pw;
StringHash(const string& s, ull P) : h(s.size() + 1, 0), pw(s.size() + 1, 1) {
for (size_t i = 0; i < s.size(); i++) {
h[i + 1] = (mulmod(h[i], P) + (unsigned char)s[i]) % MOD;
pw[i + 1] = mulmod(pw[i], P);
}
}
ull get(int l, int r) const { // хэш s[l, r): H[r] - H[l] * P^(r-l)
return (h[r] + MOD - mulmod(h[l], pw[r - l])) % MOD;
}
};190:35 Даны строка и шаблон $T$. Нужно найти все места, где $T$ встречается «с точностью до одного символа» (в разборе: окно равно шаблону без учёта одной позиции). Условие в записи передано нечётко; здесь разобран вариант «в окне длины $|T|$ не больше одной позиции с различающимся символом». Есть два подхода.
191:52 «Пацанский» способ — бинарный поиск плюс хэши за $O(n\log n)$: бинпоиском находим длину наибольшего общего префикса окна и шаблона (проверяя равенство хэшами), находим позицию различающегося символа и проверяем хэшем, что оставшиеся суффиксы совпадают. 193:16 «Элегантный» способ за $O(n)$: для каждого окна нужно знать $L_i$ — сколько первых символов окна совпало с началом $T$ — и $R_i$ — сколько последних символов окна совпало с концом $T$. $L_i$ — это Z-функция строки $T\#S$; $R_i$ получаем той же Z-функцией, развернув обе строки. Окно подходит, если $L_i+R_i\ge|T|-1$.
// Где в тексте s окно длины m = |t| отличается от t не более чем в одной позиции? Через Z-функцию, за O(n + m)
vector<int> oneMismatch(const string& s, const string& t) {
int n = s.size(), m = t.size();
vector<int> zl = zFunction(t + '#' + s); // zl[m+1+i] — общий префикс t и s[i..]
string rt(t.rbegin(), t.rend()), rs(s.rbegin(), s.rend());
vector<int> zr = zFunction(rt + '#' + rs); // общий суффикс t и s[..j]
vector<int> res;
for (int i = 0; i + m <= n; i++) {
int L = min(zl[m + 1 + i], m); // сколько первых символов окна совпало с началом t
int R = min(zr[m + 1 + (n - 1 - (i + m - 1))], m); // сколько последних — с концом t
if (L + R >= m - 1) res.push_back(i); // не совпала не более чем одна позиция
}
return res;
}196:06 Ещё предложили сравнивать начало Z-функцией, а оставшуюся часть — хэшами; так тоже можно, но это «полу ни туда ни сюда»: с чистыми Z-функциями решение получается без вероятности коллизии хэшей.
196:56 Дан граф. Нужно посчитать количество пар вершин $(u,v)$, являющихся «двойниками»: если взять множество соседей $u$ без $v$ и множество соседей $v$ без $u$, то эти множества должны совпасть. 197:57 Чтобы быстро сравнивать множества, их хэшируют: каждой вершине назначаем случайное $64$-битное число, а хэш множества — это xor всех чисел вершин множества.
199:01 Определим $H(v)$ — хэш множества соседей $v$ и $H[v]$ — хэш множества соседей вместе с самой вершиной $v$ (xor с числом $v$). Пара $(u,v)$ — двойники ровно в двух случаях: если $u$ и $v$ не соединены ребром, то должно быть $H(u)=H(v)$; если соединены, то должно быть $H[u]=H[v]$. 200:01 Осталось посчитать, сколько среди всех этих хэшей одинаковых пар: можно отсортировать, использовать unordered_map или словарь в Питоне.
// Количество пар вершин (u, v), у которых N(u) \ {v} = N(v) \ {u} («двойники»), g — список смежности
long long countTwins(const vector<vector<int>>& g) {
int n = g.size();
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<unsigned long long> r(n), open(n, 0), closed(n);
for (auto& x : r) x = rng(); // каждой вершине — случайное 64-битное число
for (int v = 0; v < n; v++) {
for (int u : g[v]) open[v] ^= r[u]; // хэш множества соседей — xor их чисел
closed[v] = open[v] ^ r[v]; // хэш множества соседей вместе с самой вершиной
}
auto pairsWithEqual = [&](vector<unsigned long long> h) {
sort(h.begin(), h.end());
long long res = 0;
for (int i = 0, j; i < n; i = j) {
j = i;
while (j < n && h[j] == h[i]) j++;
res += (long long)(j - i) * (j - i - 1) / 2; // пары внутри группы одинаковых хэшей
}
return res;
};
return pairsWithEqual(open) + pairsWithEqual(closed); // несмежные пары + смежные пары
}201:28 Дана строка; посчитать количество подстрок, которые являются палиндромами. Опять два подхода: за $O(n)$ и за $O(n\log n)$. 202:14 Чтобы не разбирать отдельно чётные и нечётные палиндромы, между соседними символами (и по краям) вставляют решётки «#» — тогда все палиндромы становятся нечётными, и можно рассматривать только «центр»: палиндром #a#b#b#a# нечётный, а «чётный» исходный abba превратился в нечётный с центром на «#». 202:50 Для каждой позиции нужно посчитать радиус — насколько большой палиндром заканчивается с этим центром. Это делает алгоритм Манакера за $O(n)$: он похож на Z-функцию — если мы внутри самого правого найденного палиндрома, то подсматриваем радиус из «отражённой» позиции и расширяем символами.
204:39 Подход за $O(n\log n)$: бинарный поиск по длине радиуса, а равенство «слева направо» и «справа налево» проверяется хэшами (префиксные хэши считаем в обе стороны).
// Число подстрок-палиндромов (пар l <= r) за O(n): вставляем '#' между символами, чтобы все палиндромы стали нечётными
long long countPalindromes(const string& s) {
string t = "#";
for (char c : s) { t += c; t += '#'; }
int n = t.size();
vector<int> rad(n, 0); // rad[i] — наибольшее k, при котором t[i-k..i+k] — палиндром
for (int i = 0, l = 0, r = -1; i < n; i++) { // [l, r] — самый правый найденный палиндром
int k = (i > r) ? 0 : min(rad[l + r - i], r - i); // зеркальное значение
while (i - k - 1 >= 0 && i + k + 1 < n && t[i - k - 1] == t[i + k + 1]) k++;
rad[i] = k;
if (i + k > r) l = i - k, r = i + k;
}
long long total = 0;
for (int i = 0; i < n; i++) total += (rad[i] + 1) / 2; // сколько палиндромов исходной строки имеют этот центр
return total;
}206:23 Нужно построить много различных строк с одинаковым хэшем, то есть «сломать» заданный хэш. Идея: возьмём два символа A и B (коды $65$ и $66$). Для полинома с основанием $31$ (как у String.hashCode в Java) двухсимвольные строки «Aa» и «BB» дают одно и то же: $65\cdot31+97=2112=66\cdot31+66$ — совершенно разные строки с одинаковым хэшем. 207:56 Дальше можно просто ставить такие блоки подряд, менять их местами и как угодно «настакивать»: из $k$ блоков получается $2^k$ различных строк, и хэш у них один и тот же — любого модуля, потому что при одинаковой длине блоков значения совпадают как целые числа.
// Полином с основанием 31 (как String.hashCode в Java): «Aa» и «BB» дают одно и то же значение 65*31 + 97 = 66*31 + 66 = 2112.
// Составляем строку из k блоков, в каждом выбираем «Aa» или «BB» — получаем 2^k разных строк с одинаковым хэшем при любом модуле.
vector<string> collidingStrings(int k) {
vector<string> res = {""};
for (int i = 0; i < k; i++) {
vector<string> nxt;
for (auto& s : res) { nxt.push_back(s + "Aa"); nxt.push_back(s + "BB"); }
res = nxt;
}
return res;
}208:54 Даны два числа $P$ и $Q$ порядка $2\cdot10^9$ (основание и модуль хэша), и строчные латинские буквы; нужно найти две различные строки с одинаковым хэшем. 209:55 Это парадокс дней рождения: в комнате из $23$ человек вероятность того, что у каких-то двоих совпадёт день рождения, уже $50\%$. Если случайных значений хэша набрать порядка $\sqrt{\text{модуль}}$, то с вероятностью около $50\%$ какие-то два совпадут. 210:36 Для $Q\approx2\cdot10^9$ это $\sqrt{2\cdot10^9}\approx5\cdot10^4$ строк: генерируем случайные строки (длиной около $100$, можно и меньше) и сохраняем хэши в словарь; как только значение повторилось у двух разных строк, коллизия найдена.
// Две разные строки из строчных букв с одинаковым хэшем sum(s[i] * p^i) mod q: парадокс дней рождения.
// Достаточно порядка sqrt(q) случайных строк.
pair<string, string> findCollision(long long p, long long q) {
mt19937 rng(12345);
unordered_map<long long, string> seen;
while (true) {
string s(20, 'a');
for (char& c : s) c = 'a' + rng() % 26;
long long h = 0, pw = 1;
for (char c : s) { h = (h + c * pw) % q; pw = pw * p % q; }
auto it = seen.find(h);
if (it != seen.end() && it->second != s) return {it->second, s};
seen[h] = s;
}
}211:24 Практический вывод. Если вы считаете хэши и думаете, что ошибка вызвана «неправильным решением» или коллизией, это можно легко проверить: если количество различных строк, которые вы сравниваете, сопоставимо с корнем из модуля, то велик шанс коллизии, и приходится использовать двойные хэши (два разных модуля) либо модуль побольше (например, $2^{61}-1$).
212:39 Даны четыре списка $A,B,C,D$ длиной до $2500$. Нужно посчитать количество четвёрок индексов $(x,y,z,t)$ таких, что $A_x+B_y+C_z+D_t=0$. Перебирать $n^4$ слишком долго — «срежем два раза»: условие равносильно $A_x+B_y=-(C_z+D_t)$. 213:58 Перебираем явно все пары — считаем все суммы $a+b$ (их $n^2\approx6{,}25\cdot10^6$) и все $-(c+d)$, и нужно посчитать, сколько способов их «закомбинировать»: тут, казалось бы, помогает unordered_map.
214:37 Но на проверке unordered_map (и даже другие «известные» хэш-таблицы) падает по времени или памяти: слишком тяжёлая структура и слишком много пар. 215:20 В идеале — отсортировать два массива и двумя указателями идти по ним, смотря на одинаковые значения. Но сортировка двух массивов по $6{,}25\cdot10^6$ элементов — $O(n^2\log n^2)$ — для этой задачи «чуть-чуть много». 217:04 Из чата подсказали: нужно написать самописную хэш-таблицу — огромный вектор (например, длины $10^7$), заполненный нулями, значение $a\cdot P+Q$ по модулю размера таблицы как индекс. 218:56 Преподаватель рассказала ещё один подход — сортировать за почти линейное время цифровой (LSD) сортировкой.
219:13 Постановка. Есть массив чисел $a_1,\dots,a_n$, каждое до $2^{32}$ (или до $10^{18}$). Классическая сортировка требует $n\log n$ сравнений; быстрее при сравнении сделать нельзя, но числа можно не только сравнивать. Сортировка подсчётом работает за $n+R$, где $R$ — диапазон значений, и при больших числах она неприменима. 220:25 Но число можно разбить на несколько «разрядов»: $a_i=x\cdot2^{16}+y$, где $x,y<2^{16}$. Можно разбить хоть на сколько частей; итоговая асимптотика — $k\cdot(n+\sqrt[k]{R})$, то есть для чисел до $10^{18}$ сортировка занимает почти линейное время с небольшой константой.
222:08 Алгоритм. Сначала сортируем пары $(x,y)$ по $y$ (младшему разряду) сортировкой подсчётом, затем — результат сортируем по $x$ (старшему) сортировкой подсчётом; каждый проход работает за $n+\text{размер разряда}$. Идти нужно «от самого младшего к самому старшему биту».
223:23 Почему это работает. Сортировка подсчётом устойчива: она сохраняет относительный порядок равных элементов (мы просто добавляем элементы в «корзины» — вектор векторов — по значению, а потом пробегаем корзины слева направо и выписываем всё подряд). После сортировки по $y$ в каждой группе с одинаковым $x$ значения $y$ идут по возрастанию. Теперь сортируем по $x$: самые маленькие $x$ оказываются в начале, а внутри каждой корзины с одинаковым $x$ порядок «по $y$» уже сохранён благодаря устойчивости. Поэтому общий порядок — по $x$, а при равных $x$ — по $y$, то есть обычный порядок на числах $x\cdot2^{16}+y$.
// LSD-сортировка 64-битных чисел: 4 прохода по 16 бит, каждый — устойчивая сортировка подсчётом
void radixSort(vector<long long>& a) {
int n = a.size();
vector<unsigned long long> x(n), y(n);
for (int i = 0; i < n; i++) x[i] = (unsigned long long)a[i] ^ (1ULL << 63); // отрицательные станут «меньше» положительных
for (int shift = 0; shift < 64; shift += 16) {
vector<int> cnt(65537, 0);
for (int i = 0; i < n; i++) cnt[((x[i] >> shift) & 0xFFFF) + 1]++;
for (int d = 0; d < 65536; d++) cnt[d + 1] += cnt[d]; // cnt[d] — где начинается блок цифры d
for (int i = 0; i < n; i++) y[cnt[(x[i] >> shift) & 0xFFFF]++] = x[i]; // устойчивая раскладка
swap(x, y);
}
for (int i = 0; i < n; i++) a[i] = (long long)(x[i] ^ (1ULL << 63));
}
// Сколько четвёрок (x, y, z, t), что A[x] + B[y] + C[z] + D[t] = 0; все списки длины n
long long countQuadruples(const vector<long long>& A, const vector<long long>& B,
const vector<long long>& C, const vector<long long>& D) {
vector<long long> L, R;
for (long long a : A) for (long long b : B) L.push_back(a + b);
for (long long c : C) for (long long d : D) R.push_back(-(c + d));
radixSort(L); radixSort(R); // можно и sort — но radix быстрее на ~6.25 млн элементов
long long res = 0;
size_t i = 0, j = 0;
while (i < L.size() && j < R.size()) { // два указателя по двум отсортированным массивам
if (L[i] < R[j]) i++;
else if (L[i] > R[j]) j++;
else {
size_t i2 = i, j2 = j;
while (i2 < L.size() && L[i2] == L[i]) i2++;
while (j2 < R.size() && R[j2] == R[j]) j2++;
res += (long long)(i2 - i) * (j2 - j); // все пары из двух блоков одинаковых значений
i = i2; j = j2;
}
}
return res;
}227:18 H. Даны два корневых дерева; нужно проверить, можно ли переименовать вершины одного, чтобы оно стало таким же, как другое (изоморфизм деревьев). 228:21 Идея: представим дерево скобочной последовательностью (ПСП). У вершины есть дети, каждое поддерево уже представлено своей ПСП; отсортируем их лексикографически и выпишем: «(», ПСП детей по порядку, «)». Изоморфные деревья дадут одинаковую строку. Хранить в лоб все строки долго, поэтому вместо строки хранят хэш такой строки, а равенство проверяют в конце.
229:21 Как хранить саму строку, не потратив $O(n^2)$ памяти и времени? Это приём «переливайка» (small-to-large). Найдём самую длинную строку среди детей и будем дописывать к ней все остальные: большую строку не трогаем. Тогда суммарная работа превращается из $n^2$ в $n\log n$: рассмотрим отдельный элемент — он переписывается только тогда, когда переходит из меньшего множества в большее, а значит, размер множества, которому он принадлежит, увеличивается хотя бы вдвое; следовательно таких переливаний у каждого элемента не более $\log n$.
231:03 Из зала подсказали другой способ — через хэши детей: собираем хэши детей в вектор, сортируем, и если такому вектору уже сопоставлен номер, берём его, иначе добавляем новый. Это тоже подходит и проще: вместо строки получаем «номер класса» поддерева. Преподаватель отметила, что ей больше нравится вариант со скобочными последовательностями (более явное представление дерева).
232:32 I. То же самое, но деревья неподвешенные — они могут быть произвольно ориентированы. Здесь нужно подвесить оба дерева так, чтобы «порядок» получался примерно одинаковый. Всё делается просто: у дерева есть диаметр; центр диаметра (вершина или ребро — две вершины) — одно и то же для изоморфных деревьев. Если диаметр (в рёбрах) нечётной длины, центром будет ребро — две вершины: подвешиваем одно дерево за один центр, а другое пробуем подвешивать за каждый из двух — достаточно, чтобы хотя бы одно сравнение дало равенство. Если диаметр чётной длины, центр — одна вершина, и подвешиваем за неё (на лекции длину диаметра, по-видимому, считали числом вершин, поэтому там «нечётная длина» — это центральная вершина).
// Изоморфизм корневых деревьев: каждому поддереву даём номер; номер определяется отсортированным списком номеров детей.
map<vector<int>, int> ids; // один общий словарь для всех сравниваемых деревьев
int canon(int v, int p, const vector<vector<int>>& g) {
vector<int> ch;
for (int u : g[v]) if (u != p) ch.push_back(canon(u, v, g));
sort(ch.begin(), ch.end());
auto it = ids.find(ch);
if (it == ids.end()) it = ids.emplace(ch, (int)ids.size()).first;
return it->second;
}
// центры дерева (одна или две вершины): последовательно срезаем листья
vector<int> centers(const vector<vector<int>>& g) {
int n = g.size();
vector<int> deg(n), cur;
for (int v = 0; v < n; v++) { deg[v] = g[v].size(); if (deg[v] <= 1) cur.push_back(v); }
int left = n;
while (left > 2) {
vector<int> nxt;
for (int v : cur) {
left--;
for (int u : g[v]) if (--deg[u] == 1) nxt.push_back(u);
}
cur = nxt;
}
return cur;
}
// изоморфны ли два (неподвешенных) дерева: подвешиваем за центры
bool isomorphic(const vector<vector<int>>& a, const vector<vector<int>>& b) {
if (a.size() != b.size()) return false;
int fa = canon(centers(a)[0], -1, a);
for (int c : centers(b))
if (canon(c, -1, b) == fa) return true; // у b подвешиваем за каждый из центров
return false;
}234:56 Дана буквенная матрица $N\times M$. Нужно найти два совпадающих квадратных фрагмента максимальной стороны. 235:46 Будем сравнивать два квадрата на равенство хэшами и бинарным поиском искать длину стороны: для фиксированной стороны берём хэши всех квадратов и смотрим, есть ли среди них два одинаковых (в разных позициях). Если квадраты размера $k$ есть, то есть и размера $k-1$ — поэтому бинпоиск корректен. Асимптотика — порядка $NM\log\min(N,M)$ (с учётом словаря). 236:14 Самое сложное — научиться считать хэш квадратика. Если сторона задана условием, нужно просто найти пару квадратов с заданной стороной.
237:41 Будем вести двумерный хэш: каждой клетке — множитель $P^{\,i}Q^{\,j}$ (по строке и по столбцу), а хэш прямоугольника — $\sum a_{ij}P^{\,r-i}Q^{\,c-j}$. Префиксные хэши считаются как двумерные префиксные суммы:
$$H_{i,j}=a_{i,j}+P\,H_{i-1,j}+Q\,H_{i,j-1}-PQ\,H_{i-1,j-1}.$$240:04 А хэш прямоугольника получается как в двумерных префиксных суммах: из «большого» прямоугольника вычитаем две полосы и прибавляем угол, домножая каждую часть на нужную степень $P^{h}$ и $Q^{w}$ (разница по строкам и по столбцам).
// Двумерный хэш: H[i][j] = a[i][j] + H[i-1][j]*PR + H[i][j-1]*PC - H[i-1][j-1]*PR*PC (по модулю 2^61 - 1)
struct Hash2D {
int n, m;
vector<vector<ull>> H;
vector<ull> prp, pcp; // степени PR и PC
Hash2D(const vector<string>& a, ull PR, ull PC) : n(a.size()), m(a[0].size()), H(n + 1, vector<ull>(m + 1, 0)),
prp(n + 1, 1), pcp(m + 1, 1) {
for (int i = 0; i < n; i++) prp[i + 1] = mulmod(prp[i], PR);
for (int j = 0; j < m; j++) pcp[j + 1] = mulmod(pcp[j], PC);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ull v = (ull)(unsigned char)a[i - 1][j - 1] + mulmod(H[i - 1][j], PR) + mulmod(H[i][j - 1], PC);
v = (v + MOD - mulmod(mulmod(H[i - 1][j - 1], PR), PC)) % MOD;
H[i][j] = v % MOD;
}
}
// хэш прямоугольника строк [r1, r2), столбцов [c1, c2)
ull get(int r1, int c1, int r2, int c2) const {
int h = r2 - r1, w = c2 - c1;
ull res = H[r2][c2];
res = (res + MOD - mulmod(H[r1][c2], prp[h])) % MOD;
res = (res + MOD - mulmod(H[r2][c1], pcp[w])) % MOD;
res = (res + mulmod(mulmod(H[r1][c1], prp[h]), pcp[w])) % MOD;
return res;
}
};
// максимальная сторона k, для которой в матрице есть два совпадающих квадрата k×k в разных местах
int maxEqualSquares(const vector<string>& a) {
mt19937_64 rng(777);
Hash2D h(a, rng() % (MOD - 1000) + 500, rng() % (MOD - 1000) + 500);
int n = a.size(), m = a[0].size();
auto exists = [&](int k) {
map<ull, pair<int,int>> seen;
for (int i = 0; i + k <= n; i++)
for (int j = 0; j + k <= m; j++) {
ull x = h.get(i, j, i + k, j + k);
auto it = seen.find(x);
if (it != seen.end()) return true; // такой квадрат уже был в другой позиции
seen[x] = {i, j};
}
return false;
};
int lo = 0, hi = min(n, m) + 1; // lo — «есть» (k = 0), hi — «нет»
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (exists(mid)) lo = mid; else hi = mid;
}
return lo;
}241:41 Даны строки $S$ и $T$. Нужно найти левый циклический сдвиг $S$ на $k$ позиций и число $d$ такие, что после сдвига каждая буква заменяется на букву, стоящую на $d$ позиций раньше (по модулю алфавита), и получается $T$. 244:00 Это очень похоже на задачу из контеста «Строки 1» (где одинаковые подстроки можно «подвигать вместе вверх и вниз»): считаем массив разностей соседних символов — он не меняется, если все буквы сдвинуть на одно и то же число. Считаем его для $S$ (циклически) и для $T$ и ищем в циклической записи $S$ такой сдвиг, который совпадает с $T$; затем $d$ определяется по одной букве.
245:28 Возможен и вариант с хэшами: перебирать все циклические сдвиги и смотреть, как меняется хэш строки при замене «минус $d$»: символы, большие $d$, сдвигаются вниз ($S_i-d$), меньшие переходят в $S_i-d+26$; нужно для каждой буквы уметь считать сумму $\sum P^{\,|S|-i}$ по позициям с этой буквой, и тогда при переходе от $d$ к $d+1$ хэш пересчитывается через такие суммы.
// Найти циклический сдвиг влево на k и число d, чтобы после сдвига и замены каждой буквы на букву на d позиций раньше (по модулю 26) вышла строка t.
// Разностный массив не меняется при одновременном сдвиге всех букв, поэтому ищем t среди разностей s по кругу.
pair<int,int> cyclicShiftAndCaesar(const string& s, const string& t) {
int n = s.size();
vector<int> ds(n), dt; // ds — циклические разности s, dt — разности t
for (int i = 0; i < n; i++) ds[i] = ((s[(i + 1) % n] - s[i]) % 26 + 26) % 26;
for (int i = 0; i + 1 < n; i++) dt.push_back(((t[i + 1] - t[i]) % 26 + 26) % 26);
// ищем dt в удвоенном ds одной Z-функцией; для n = 1 разностей нет, подойдёт k = 0
string pat(dt.begin(), dt.end()), text;
for (int i = 0; i < 2 * n; i++) text += (char)ds[i % n];
vector<int> z = zFunction(pat + (char)100 + text); // разделитель 100 — вне диапазона разностей 0..25
for (int k = 0; k < n; k++) {
if (n == 1 || z[(n - 1) + 1 + k] >= n - 1) { // окно из n-1 разностей совпало
int d = ((s[k] - t[0]) % 26 + 26) % 26;
return {k, d};
}
}
return {-1, -1};
}248:04 Последняя задача контеста (с разбором на четыре страницы) не обсуждалась — время вышло.
sync_with_stdio(false) и cin.tie(nullptr), '\n' вместо endl; fixed + setprecision для вещественных (вывод округляет); cin.ignore() перед getline.nth_element — $O(n)$ в среднем; stable_sort сохраняет порядок равных; unique — только после сортировки; для set — метод lower_bound; iota, rotate, next_permutation экономят время.self; range-based for и structured bindings сокращают код.LOCAL и _GLIBCXX_DEBUG, санитайзеры (address, undefined), отладчик среды, стресс-тестирование — обязательный инструмент.