What falls into the window
A mapping application draws only what is visible on the screen. The map objects (buildings, roads, stops) are given as rectangles with sides along the axes; a road’s rectangle may be a segment of zero width, a stop’s a point. The user moves and zooms the map, and for each position of the window we need to know how many objects intersect it. Touching counts too: an object that touches the window with an edge or a corner must be drawn.
Input
The first line holds n and q (1 ≤ n ≤ 5 · 104, 1 ≤ q ≤ 104). Then n lines with objects and q lines with windows, four integers each, x1 y1 x2 y2: 0 ≤ x1 ≤ x2 ≤ 106, 0 ≤ y1 ≤ y2 ≤ 106. The sum of all answers of one test is at most 106.
Output
For each window, the number of objects that have at least one point in common with it, on a separate line.
Examples
Example 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
Example 2
1 3 10 10 20 20 20 20 30 30 0 0 9 9 21 0 40 40
1 0 0
Limits
- Time · Python
- 14000 ms
- Time · Go
- 1000 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
Checking every object for every window is 5 · 108 checks. But almost all objects lie far from the window; we would like to discard them at once, in whole groups.
2Hint 2
Put neighbouring objects into groups of 16 and draw a rectangle around each group. If the window does not touch a group’s rectangle, none of its objects is needed. Groups can also be put into groups.
3The idea
An R-tree built by STR packing: the objects are sorted by the x of their centre, cut into √(n/16) strips, sorted by y within each strip, and taken 16 in a row per leaf. One level up the same is done with the leaves’ rectangles, and so on up to the root. A query descends only into nodes whose rectangle touches the window.
4Walkthrough
All the objects are known in advance, so the tree is built once by packing, which is sorts, O(n log n). One-by-one insertion with splitting of overflowing nodes also works, but takes longer and gives nodes about 60–70% full. The intersection of two rectangles is four comparisons with non-strict inequalities: a.x1 ≤ w.x2, w.x1 ≤ a.x2, and likewise in y. In Python it is convenient to keep the levels of the tree as flat lists of coordinates and to walk the tree with a stack.
4+Solution
5Complexity
Building is O(n log n). A query is the number of visited nodes times 16. An R-tree has no guarantee like a segment tree’s: if node rectangles overlap, a query descends into several branches. On map-like data there are few such nodes, and the limit on the sum of answers keeps the tests from forcing a solution to list everything.
There is also a solution with a guarantee if all the windows are known in advance: the objects that do not touch a window are those entirely to its left, right, below or above. Left and above at once is the intersection of two conditions, and by inclusion–exclusion the number of non-intersecting objects is assembled from four one-dimensional counts and four “corner” ones, and the corner ones are computed by a sweep line with a Fenwick tree. That is O((n + q) log n) whatever the answers.
6Common mistakes
- Brute force. This is
wrong.py: it makes it on a small test, but not on fifty thousand objects and ten thousand windows. - Strict inequalities. Touching counts (the second example), and a point object or a segment object would intersect nothing with strict inequalities.
- Recursion in Python. The tree is four or five levels deep, but a function call per node is noticeably more expensive than a stack of (level, node) pairs.