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

Задача

Сколько людей в прямоугольнике

запросы на отрезке офлайн-запросы заметающая прямая геоданные

Служба доставки выбирает, где открывать склады, и для этого ей нужно знать, сколько городов и сколько людей попадает в прямоугольник карты. Прямоугольников-кандидатов — десятки тысяч, городов — тоже. Аналитик уже выгрузил координаты городов в целых числах: в одном из тестов это настоящие города мира с населением от 20 000 человек из GeoNames, а координаты — в тысячных долях градуса, долгота первой. Ваша задача — ответить на все запросы сразу.

Город на границе прямоугольника считается попавшим в него. В одной точке может быть несколько городов.

Вход

В первой строке числа n и q (1 ≤ n, q ≤ 30 000) — число городов и прямоугольников. Дальше n строк x y w: координаты города и его население (|x|, |y| ≤ 109, 1 ≤ w ≤ 109). Дальше q строк x1 y1 x2 y2 — противоположные углы прямоугольника (x1 ≤ x2, y1 ≤ y2, все по модулю не больше 109).

Выход

q строк, по одной на прямоугольник в порядке входа: число городов в нём и их суммарное население через пробел.

Примеры

Пример 1

Вход
3 3
2 3 100
5 1 40
5 5 7
0 0 5 5
3 0 10 4
5 5 5 5
Выход
3 147
1 40
1 7

Ограничения

Время · Python
4000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
8 тестов

Разбор

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

1Подсказка 1

Перебор — каждый город против каждого прямоугольника — это 30 000 · 30 000 = 9·108 проверок. Таблица «население в клетке» по самим координатам — 4·1018 клеток. Ни то ни другое не годится. Что можно сделать с координатами, если важен только их порядок?

2Подсказка 2

Запрос «сколько городов в прямоугольнике» — это разность двух запросов «сколько городов западнее x и с широтой от y1 до y2». Если идти по городам с запада на восток и складывать их в структуру по широте, на такой вопрос она отвечает в момент, когда пройдены все города западнее x.

3Идея

Сожмём широты городов в номера от 0 до m − 1 и заведём дерево Фенвика на m ячеек — для числа городов и для населения. Города отсортируем по долготе. Каждый прямоугольник превращается в два вопроса к дереву: в момент, когда в дереве лежат все города с долготой меньше x1, вычтем сумму по номерам широт от lb(y1) до ub(y2) − 1, а в момент, когда лежат все с долготой не больше x2, — прибавим. Все 2q моментов отсортируем и пройдём по городам один раз.

4Разбор

Момент — это просто число городов, уже добавленных в дерево: bisect_left(xs, x1) для западного края и bisect_right(xs, x2) для восточного, где xs — долготы городов по возрастанию. Границы по широте переводятся в номера так же: lb(y1) — сколько различных широт меньше y1, ub(y2) — сколько не больше y2. Широты, которых нет среди городов, при этом не нужны: двоичный поиск отвечает и для них. Почему такой перевод точен, доказано в статье о сжатии координат.

Обратите внимание, что сжимать долготы не нужно: по ним мы не заводим массив, а только сортируем. Сжатие нужно ровно той оси, по которой строится дерево.

Население в сумме доходит до 3·1013 — в 32 бита не помещается; в Python это неважно, а в Go тип int 64-битный.

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

Сортировки — O(n log n + q log q), добавление городов и ответы — O((n + q) log n). Память O(n + q). На тесте с городами мира эталон на Python укладывается в десятые доли секунды, а перебор не успевает.

6Типичные ошибки
  • Перебор. Верный, но 9·108 проверок не укладываются во время даже на Go с запасом, а на Python — тем более.
  • Строгие и нестрогие границы. Город на западном краю должен попасть в ответ, поэтому из прямоугольника вычитают города с долготой строго меньше x1 (bisect_left), а прибавляют — с долготой не больше x2 (bisect_right). Перепутанная граница ломает первый пример, где граница проходит через город.
  • Массив по самим широтам. Широты до 109 по модулю — массив на два миллиарда ячеек не поместится в 256 МБ. Ровно для этого и нужно сжатие.
  • Запросы в порядке входа. Если отвечать на вопросы к дереву не в порядке моментов, а как они пришли, придётся то добавлять города, то вынимать их обратно — лишняя работа и лишние ошибки. Отсортируйте все 2q вопросов по моменту; в каком порядке идут вычитание и прибавление в один и тот же момент, неважно.

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

TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи DS Структура данных Дерево Фенвика Суммы на префиксе с изменениями за O(log n) в одном массиве: блоки длиной в младшую единицу номера. O(log n) на сумму префикса и на изменение 2 задачи
Каталог алгоритмов