Что попало в окно
Картографическое приложение рисует только то, что видно на экране. Объекты карты — здания, дороги, остановки — заданы прямоугольниками со сторонами вдоль осей; у дороги прямоугольник может быть отрезком нулевой ширины, у остановки — точкой. Пользователь двигает и масштабирует карту, и для каждого положения окна нужно знать, сколько объектов с ним пересекается. Касание тоже считается: объект, который задевает окно краем или углом, рисовать нужно.
Вход
В первой строке — n и q (1 ≤ n ≤ 5 · 104, 1 ≤ q ≤ 104). Дальше n строк с объектами и q строк с окнами, по четыре целых числа x1 y1 x2 y2: 0 ≤ x1 ≤ x2 ≤ 106, 0 ≤ y1 ≤ y2 ≤ 106. Сумма всех ответов одного теста не больше 106.
Выход
Для каждого окна — число объектов, у которых с ним есть хотя бы одна общая точка, в отдельной строке.
Примеры
Пример 1
4 4 0 0 4 3 2 1 6 5 8 8 9 9 5 0 5 7 3 2 4 4 6 6 10 10 0 6 4 9 4 0 5 0
2 1 0 2
Пример 2
1 3 10 10 20 20 20 20 30 30 0 0 9 9 21 0 40 40
1 0 0
Ограничения
- Время · Python
- 14000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверить каждый объект для каждого окна — 5 · 108 проверок. Но почти все объекты лежат далеко от окна; хочется отбрасывать их сразу целыми группами.
2Подсказка 2
Сложите соседние объекты в группы по 16 и опишите вокруг каждой группы прямоугольник. Если окно не задевает прямоугольник группы, ни один её объект не нужен. Группы тоже можно складывать в группы.
3Идея
R-дерево, построенное упаковкой STR: объекты сортируются по центру по x, режутся на √(n/16) полос, внутри полосы сортируются по y и берутся по 16 подряд в лист. Уровнем выше то же самое делается с прямоугольниками листьев — и так до корня. Запрос спускается только в узлы, чей прямоугольник задевает окно.
4Разбор
Все объекты известны заранее, поэтому дерево строится один раз упаковкой — это сортировки, O(n log n). Вставка по одному с разбиением переполненных узлов тоже работает, но дольше и даёт узлы, заполненные примерно на 60–70 %. Пересечение двух прямоугольников — четыре сравнения с нестрогими неравенствами: a.x1 ≤ w.x2, w.x1 ≤ a.x2 и так же по y. В Python удобно хранить уровни дерева плоскими списками координат и обходить дерево стеком.
4+Решение
5Сложность
Построение — O(n log n). Запрос — число посещённых узлов, умноженное на 16. Гарантии, как у дерева отрезков, у R-дерева нет: если прямоугольники узлов перекрываются, запрос спускается в несколько ветвей. На данных, похожих на карты, узлов немного; ограничение на сумму ответов не даёт тестам заставить решение перечислить всё.
Есть и решение с гарантией, если все окна известны заранее: объекты, не задевающие окно, — это те, что целиком левее, правее, ниже или выше него. Левее и выше сразу — пересечение двух условий, и по формуле включений и исключений число непересекающихся объектов собирается из четырёх одномерных подсчётов и четырёх «угловых», а угловые считаются заметающей прямой с деревом Фенвика. Это O((n + q) log n) при любых ответах.
6Типичные ошибки
- Перебор. Это
wrong.py: на маленьком тесте он успевает, на пятидесяти тысячах объектов и десяти тысячах окон — нет. - Строгие неравенства. Касание считается (второй пример), а объект-точка или объект-отрезок со строгими неравенствами не пересёк бы ничего.
- Рекурсия в Python. Глубина дерева — четыре-пять уровней, но вызов функции на каждый узел заметно дороже, чем стек из пар (уровень, узел).