Здравствуйте, Товарищи!!!😎😎😎 Сегодня разбираем один из важнейших алгоритмических приёмов — метод сканирующей прямой (или просто scanline). Этот подход довольно часто встречается в задачах на геометрию, интервалы, события и т. д. На олимпиаде ШВБ по информатике одна задачек решалась именно этим алгосом, так что смотрим и запоминаем!!😎 Определение & Идея Вместо того чтобы проверять каждую точку или отрезок по отдельности, мы сортируем все интересные события (начала, концы отрезков, запросы и т.д.) и проходим по ним слева направо, поддерживая нужные параметры. Изменения происходят только в "интересных точках" — началах и концах отрезков. Разберем парочку известных задачек Задача 1 Дано n отрезков [l_i, r_i]. Найти точку, покрытую максимальным числом отрезков. Идея Каждое начало отрезка — событие +1, конец — -1. Сортируем события по координате (при равенстве сначала начала). Идём слева направо, поддерживая cnt — текущее число активных отрезков. И получаем максимум cnt — это наш ответ. struct event { int x, type; }; int scanline(vector<pair<int, int>> segments) { &nbsp;&nbsp;&nbsp; vector<event> events; &nbsp;&nbsp;&nbsp; for (auto [l, r] : segments) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; events.push_back({l, 1}); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; events.push_back({r, -1}); &nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp; sort(events.begin(), events.end(), { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return (a.x < b.x || (a.x == b.x && a.type > b.type)); &nbsp;&nbsp;&nbsp; }); &nbsp;&nbsp;&nbsp; int cnt = 0, res = 0; &nbsp;&nbsp;&nbsp; for (auto e : events) { &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cnt += e.type; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; res = max(res, cnt); &nbsp;&nbsp;&nbsp; } &nbsp;&nbsp;&nbsp; return res; } По сложности вышло O(n log n). Как вы видите, алгос не супер сложный Задача 2 Найти суммарную длину объединения всех [l_i, r_i] Идея Как и раньше, отсортируем события и пойдём слева направо: Если cnt > 0, добавляем к ответу длину между текущей и предыдущей координатой; При входе в отрезок cnt++, при выходе — cnt--. Работает за O(n log n) int cnt = 0, res = 0, prev = -inf; for (auto e : events) { &nbsp;&nbsp;&nbsp; if (prev != -inf && cnt > 0) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; res += e.x - prev; &nbsp;&nbsp;&nbsp; cnt += e.type; &nbsp;&nbsp;&nbsp; prev = e.x; } Итоги Как вы видите, сканлайн это: Довольно универсальный алгос для решения задачек Объединяет подходы из ДП, геомы и др. Практика (LeetCode) Count Days Without Meetings Maximum Beauty of an Array After Applying Operation Shifting Letters II Two Best Non-Overlapping Events Merge Intervals (обязательно прорешайте эту задачку!!! похожая формулировка была на отборе ШВБ + иногда дают на алгособесе в Яндекс) Interval List Intersections Ещё больше разборов и подборок задач на нашей 3х месячной олимпиадной смене по информатике @postupashki_prog