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

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

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

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

Пусть, дан набор из \(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,\ldots,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