Сканирующая прямая

Общая идея этого алгоритма заключается в сортировке точек и затем проходу по ним(по этому алгоритм так и называется).

Давайте разберем несколько задач на эту тему и лучше поймем алгоритм.

Точка, покрытая наибольшим количеством отрезков

Пусть, дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i,r_i]$. Требуется найти любую точку на прямой, покрытую наибольшим количеством отрезков.

Понятно, что каждую точку прямой мы проверить не можем. В каких точках прямой может происходить смена количества отрезков, которыми она покрыта? Только в началах или концах данных отрезков. Назовем такие точки интересными. Так как смена ответа может происходить только в интересной точке, максимум достигается так же в какой-то из интересных точек. Отсюда сразу следует решение за $O(n^2)$: просто перебрать все интересные точки и проверить для них ответ.

Это решение можно улучшить. Отсортируем интересные точки по возрастанию координаты. Пройдем по интересным точкам слева направо, поддерживая количество отрезков $c$, которые покрывают данную точку. Если в данной точке начинается отрезок, то надо прибавить 1 к $c$, а если заканчивается вычесть 1 из $c$. После этого надо попробовать обновить ответ на задачу.

Заметим, что если координаты двух интересных точек совпали, чтобы получить правильный ответ, сначала надо рассмотреть начала отрезков, а потом концы.

Как такое писать: нужно представить интересные точки в виде структур с полями “координата” и “тип” (начало/конец) и отсортировать со своим компаратором. Удобно начало отрезка обозначать +1, а конец -1, чтобы прибавлять к $c$ именно это значение.

struct event{
    int x, type;
};
int main(){
    int n;
    cin >> n;
    vector<event> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].type;
    sort(a.begin(), a.end(), [](const event& e1, const event& e2) {
        return e1.x == e2.x ? e1.type < e2.type : e1.x < e2.x; 
    });
}

Такое решение работает за $O(n\log n)$ на сортировку. Этот подход называется методом сканирующей прямой.

Скольким отрезкам принадлежит точка

Пусть, теперь надо для $q$ точек (не обязательно являющихся концами отрезков) ответить на вопрос: скольким отрезкам принадлежит данная точка?

Воспользуемся следующим приемом: сразу считаем все запросы и сохраним их, чтобы потом ответить на все сразу. Добавим точки запросов в массив интересных точек с новым типом 0, который будет означать, что в этой точке надо ответить на запрос. В случае равенства координат запросы должны идти после начал и до концов. Точно так же отсортируем точки и пройдем по точкам слева направо, поддерживая $c$ и запоминая ответы на запросы. Асимптотика $O((n+q)\log (n+q))$.

Количество пересекающихся отрезков

Пусть, дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i,r_i]$. Требуется для каждого отрезка сказать, с каким количеством отрезков он пересекается (может иметь общую точку или быть вложенным).

Вместо того, чтобы считать количество отрезков, с которыми отрезок пересекается, посчитаем количество отрезков, с которыми он не пересекается, и вычтем это число из $n-1$. Отрезок $[l_1,r_1]$ может не пересекаться с другим отрезком $[l_2,r_2]$, только если $r_2<l_1$ или $r_1<l_2$. Количество отрезков для каждого из случаев легко подсчитать.

Будем считать, что изначально ответ для всех отрезков равен $n-1$. Запишем все интересные точки, отсортируем их. Пройдем слева направо, поддерживая число отрезков, которые уже закончились (изначально 0) и число отрезков, которые еще не начались (изначально $n-1$). При обработке очередной точки, если это начало, вычитаем из ответа для этого отрезка число уже закончившихся, а если конец, то вычитаем количество еще не начавшихся. После этого изменяем значение соответствующего счетчика.

Заметим, что теперь в структуре точки необходимо хранить еще и номер отрезка, которому она принадлежала. Время работы $O(n\log n)$.

Длина объединения отрезков

Пусть, дан набор из $n$ отрезков на прямой, заданных координатами начал и концов $[l_i,r_i]$. Требуется нати длину их объединения.

Как обычно, отсортируем интересные точки и при проходе поддерживаем число отрезков, покрывающих данную точку. Если оно больше 0, то отрезок который мы прошли с прошлой рассмторенной точки принадлежит объединению. Время работы $O(n\log n)$.

Сжатие координат

Это общая идея, которая может оказаться полезной. Пусть, есть $n$ чисел $a_1,\dots ,a_n$. Хотим, преобразовать $a_i$ так, чтобы равные остались равными, разные остались разными, но все они были от 0 до $n-1$. Для этого надо отсортировать числа, удалить повторяющиеся и заменить каждое $a_i$ на его индекс в отсортированном массиве.

int a[n], all[n];
for (int i = 0; i < n; ++i) {
    cin >> a[i];
    all[i] = a[i];
}
sort(all, all + n);
m = unique(all, all + n) - all; // теперь m - число различных координат
for (int i = 0; i < n; ++i)
    a[i] = lower_bound(all, all + m, x[i]) - all;

Задание

Решите как можно больше задач из контеста https://informatics.msk.ru/mod/statements/view.php?id=33318