How many people in a rectangle
A delivery service is choosing where to open warehouses, and for this it needs to know how many cities and how many people fall within a rectangle of the map. There are tens of thousands of candidate rectangles, and as many cities. An analyst has already exported the coordinates of the cities as integers: in one of the tests these are the real cities of the world with 20,000 people or more from GeoNames, with coordinates in thousandths of a degree, longitude first. Your task is to answer all the queries at once.
A city on the boundary of a rectangle counts as inside it. Several cities may be at the same point.
Input
The first line holds the numbers n and q (1 ≤ n, q ≤ 30,000), the number of cities and rectangles. Then n lines x y w: a city's coordinates and population (|x|, |y| ≤ 109, 1 ≤ w ≤ 109). Then q lines x1 y1 x2 y2, opposite corners of a rectangle (x1 ≤ x2, y1 ≤ y2, all at most 109 in absolute value).
Output
q lines, one per rectangle in input order: the number of cities in it and their total population, separated by a space.
Examples
Example 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
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Brute force, each city against each rectangle, is 30,000 · 30,000 = 9·108 checks. A table “population per cell” over the coordinates themselves is 4·1018 cells. Neither will do. What can be done with the coordinates if only their order matters?
2Hint 2
The query “how many cities are in a rectangle” is the difference of two queries “how many cities lie west of x with latitude from y1 to y2”. If you go through the cities from west to east and add them into a structure by latitude, it answers such a question at the moment all cities west of x have been passed.
3The idea
Compress the cities' latitudes into ranks from 0 to m − 1 and set up a Fenwick tree of m cells, for the number of cities and for the population. Sort the cities by longitude. Each rectangle turns into two questions to the tree: at the moment the tree holds all cities with longitude less than x1, subtract the sum over latitude ranks from lb(y1) to ub(y2) − 1, and at the moment it holds all with longitude at most x2, add it. Sort all 2q moments and go through the cities once.
4Walkthrough
A moment is simply the number of cities already added to the tree: bisect_left(xs, x1) for the western edge and bisect_right(xs, x2) for the eastern one, where xs is the cities' longitudes in increasing order. The latitude bounds are turned into ranks the same way: lb(y1), how many distinct latitudes are smaller than y1; ub(y2), how many are no greater than y2. Latitudes absent from the cities are not needed for this: binary search answers for them too. Why this translation is exact is proved in the article on coordinate compression.
Note that the longitudes need not be compressed: no array is set up over them, they are only sorted. Compression is needed for exactly the axis the tree is built over.
The total population reaches 3·1013, which does not fit in 32 bits; in Python this does not matter, and in Go int is 64-bit.
4+Solution
5Complexity
Sorting is O(n log n + q log q), adding cities and answering O((n + q) log n). Memory O(n + q). On the test with the world's cities the Python reference finishes in tenths of a second, while brute force does not make it.
6Common mistakes
- Brute force. Correct, but 9·108 checks do not fit in the time even in Go with a margin, let alone Python.
- Strict and non-strict bounds. A city on the western edge must be counted, so the rectangle subtracts the cities with longitude strictly less than x1 (
bisect_left) and adds those with longitude at most x2 (bisect_right). A mixed-up bound breaks the first sample, where a boundary passes through a city. - An array over the latitudes themselves. Latitudes up to 109 in absolute value would need an array of two billion cells, which does not fit in 256 MB. That is exactly what compression is for.
- Queries in input order. If questions to the tree are answered as they came rather than in order of moments, cities have to be added and then taken out again: extra work and extra mistakes. Sort all 2q questions by moment; the order of a subtraction and an addition at the same moment does not matter.
Algorithms behind it
O(n log n) to compress
2 problems
DS
Data structure
Fenwick tree
Prefix sums with updates in O(log n) in a single array: blocks as long as the lowest one bit of the index.
O(log n) per prefix sum and per update
2 problems