Афиши на заборе
Вдоль ограды стройки длиной в миллиард миллиметров расклеивают афиши — одну за другой, каждая новая ложится поверх тех, что уже висят. Афиша занимает отрезок ограды от l-го до r-го миллиметра включительно, высота у всех одинаковая, так что новая афиша закрывает старые там, где они пересекаются. Когда расклейщики ушли, прохожий насчитал, сколько разных афиш видно хотя бы краешком — хотя бы одним миллиметром. Посчитайте и вы.
Вход
В первой строке число афиш n (1 ≤ n ≤ 100 000). Дальше n строк l r (1 ≤ l ≤ r ≤ 109) в том порядке, в каком афиши клеили.
Выход
Одно число — сколько афиш видно хотя бы одним миллиметром.
Примеры
Пример 1
3 1 10 1 4 6 10
3
Пример 2
3 1 10 1 4 5 10
2
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 9 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Ограду длиной в миллиард по миллиметрам не покрасить. Но концов у афиш всего 2n. Что происходит с оградой между двумя соседними концами?
2Подсказка 2
Первый пример: [1, 10], поверх [1, 4] и [6, 10]. Если концам 1, 4, 6, 10 раздать номера 0, 1, 2, 3 и красить клетки от номера l до номера r, первая афиша окажется закрытой. А на ограде она видна. Где пропал пятый миллиметр?
3Идея
Сжимать нужно не точки, а элементарные отрезки. Афиша [l, r] занимает полуинтервал [l, r + 1). Разрежем ограду во всех точках l и r + 1: между соседними разрезами ни одна афиша не начинается и не кончается, поэтому каждый такой кусок либо целиком под афишей, либо целиком вне её, и его можно считать одной клеткой. Клеток не больше 2n, и раскраска клеток повторяет раскраску ограды.
4Разбор
Красить клетки в порядке расклейки, перезаписывая старые цвета, можно, но это O(n · клеток) в худшем случае — например, когда каждая новая афиша закрывает всю ограду. Удобнее идти с конца: последняя афиша видна там, куда её положили, предпоследняя — там, где её не закрыла последняя, и так далее. Клетку, которую уже закрасили, больше трогать не нужно. Чтобы перепрыгивать через закрашенные клетки быстро, храним для каждой клетки ссылку «следующая незакрашенная не левее меня» и сжимаем пути, как в системе непересекающихся множеств. Афиша видна, если в её отрезке нашлась хоть одна незакрашенная клетка.
Во втором примере [1, 10] закрыта целиком: [1, 4] и [5, 10] касаются, промежутка между ними нет. Разрезы 1, 5, 11 — две клетки, обе закрашены поздними афишами. Сжатие по концам ответит здесь верно — потому эта ошибка и живёт долго: на многих входах она не видна.
4+Решение
5Сложность
Сортировка разрезов — O(n log n). Каждая клетка закрашивается один раз, а прыжки по ссылкам со сжатием путей почти ничего не добавляют: всего O(n log n).
6Типичные ошибки
- Сжатие по концам. Самая частая ошибка — разбирается в подсказках. На первом же примере она отвечает 2 вместо 3.
- Добавить точки «между» без разбора. Иногда к концам добавляют r + 1 или l − 1, но работают по-прежнему с клетками «от номера l до номера r включительно». Это тоже работает, если аккуратно, но проще и надёжнее перейти к полуинтервалам [l, r + 1): тогда клетка — ровно кусок между соседними разрезами, и никаких особых случаев нет.
- Перекраска в прямом порядке. Верна, но квадратична: на тесте, где каждая афиша шире предыдущей, она красит одни и те же клетки сто тысяч раз.