CS
Задачник Базовый курс EN

Задача

Покрытие снимками

заметающая прямая дерево отрезков карты и навигация изображения

Спутник снимает Землю кадрами. На карте в проекции, где расстояния измеряют в метрах, каждый кадр — прямоугольник со сторонами вдоль осей. Соседние кадры одного витка перекрываются, витки пересекают друг друга, одно место снимают по многу раз. Какая площадь карты покрыта хотя бы одним кадром?

Вход

В первой строке — n (1 ≤ n ≤ 50 000), число кадров. Дальше n строк: x1 y1 x2 y2 — левый нижний и правый верхний углы кадра, целые, 0 ≤ x1 < x2 ≤ 109, 0 ≤ y1 < y2 ≤ 109. Кадры могут совпадать.

Выход

Площадь объединения кадров — одно целое число.

Примеры

Пример 1

Вход
3
0 0 4 3
2 1 6 5
5 0 7 2
Выход
27

Пример 2

Вход
3
0 0 10 10
2 2 4 4
0 0 10 10
Выход
100

Ограничения

Время · Python
13500 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
9 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Проведите вертикальную прямую и двигайте её слева направо. Между двумя соседними левыми или правыми краями кадров длина накрытой части прямой не меняется — площадь этой полосы равна длине, умноженной на ширину полосы.

2Подсказка 2

Осталось быстро знать накрытую длину после каждого события: на прямой добавляется или убирается отрезок [y1, y2]. Пересчитывать её заново по всем полосам — O(n) на событие и O(n²) всего.

3Идея

Заметающая прямая и дерево отрезков над сжатыми координатами y. Узел хранит, сколько отрезков накрывают его целиком (cnt), и накрытую длину внутри него (cov): если cnt > 0, это вся длина узла, иначе сумма детей. Добавление и удаление отрезка трогают O(log n) узлов, а ответ на «сколько накрыто» лежит в корне.

4Разбор

Различные y сортируем — получаем не больше 2n − 1 элементарных полос. Каждый кадр даёт два события: (x1, +1) и (x2, −1). События идут по возрастанию x; перед обработкой события к ответу прибавляется cov[корень] · (x − xпред). Отложенные операции не нужны: отрезок, добавленный в узлы, удаляется ровно из тех же узлов — разбиение [a, b) на узлы дерева однозначно, — поэтому cnt никогда не становится отрицательным и не спускается к детям. Это доказано в разделе статьи о площади объединения.

4+Решение
5Сложность

O(n log n): сортировки и 2n обновлений дерева по O(log n). Ответ доходит до 1018 — в Go и C нужен 64-битный тип, он помещается.

6Типичные ошибки
  • Пересчёт накрытой длины целиком. Это wrong.py: на тысяче кадров он успевает, на пятидесяти тысячах — нет.
  • Сумма площадей минус попарные пересечения. Если место сняли трижды, вычтется лишнее: формула включений и исключений требует всех пересечений, а их экспоненциально много.
  • Поиск максимума вместо подсчёта. В узле нужен счётчик, а не флаг «накрыт»: когда из двух накрывших узел кадров один кончился, узел остаётся накрытым.
  • Точки вместо полос. Лист дерева — промежуток между соседними различными y, а не сама координата; иначе теряется длина между ними.

Алгоритмы задачи

GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи DS Структура данных Дерево отрезков Минимум, максимум и сумма на любом отрезке с изменениями на ходу: оба действия за O(log n). O(log n) на запрос и на изменение 2 задачи TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи
Каталог алгоритмов