A cut along a meridian
A cartographer keeps towns in a treap: the key is longitude, the priority population, and a parent has a higher priority than its children. To divide the map along a meridian, the tree is cut by the split operation: starting from the root, a node with a key less than the meridian goes to the western part and the cut continues in its right subtree, while a node with a key not less than the meridian goes to the eastern part and the cut continues in its left subtree. The cut ends when there is nowhere to go. The cartographer wants to know in advance how many nodes each cut will pass, for each of many meridians, and each time for the original tree.
All keys are distinct and all priorities are distinct, so the tree is uniquely determined. The third and fourth tests are 45,227 GeoNames towns of 10,000 people or more with population as priority, and 12,392 towns of 50,000 or more with latitude as priority. A town’s key there is its longitude in thousandths of a degree, multiplied by 100,000, plus the town’s number, so that keys do not coincide; the meridians in the third test are every whole degree.
Input
The first line holds n (1 ≤ n ≤ 10⁵). Then n lines x p, a node’s key and priority (|x| ≤ 10¹², 1 ≤ p ≤ 10¹⁸), in any order. Then q (1 ≤ q ≤ 10⁵) and q lines of meridians m (|m| ≤ 10¹²).
Output
For each meridian, how many nodes a cut of the original tree along it will pass.
Examples
Example 1
5 10 5 20 9 30 7 40 3 50 8 7 5 15 25 30 35 45 60
2 2 3 3 4 4 2
Example 2
4 1 1 2 2 3 3 4 4 4 0 1 3 5
4 4 3 1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 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
The tree itself is built in O(n): the keys are sorted, and then the right-edge stack from the article does the work. But even so, an honest cut for each meridian walks a path from the root down, and a tree with non-random priorities can be a stick: in the fifth test the priority grows along with the key.
2Hint 2
A cut along m follows the same path as a search for a key m that is not in the tree, and ends at an empty link. Between which two keys in order does this empty link lie?
3Hint 3
Let a be the largest key less than m and b the smallest key not less than m. In a search tree, of two keys adjacent in order one is always an ancestor of the other. Under which of them hangs the empty link where the cut ends?
4The idea
The answer for a meridian is the depth of the deeper of the two neighbours a and b (if one is missing, the depth of the other). The depths of all nodes are computed once by a traversal of the tree, and a meridian’s neighbours are found by binary search over the sorted keys. In total O((n + q) log n).
5Walkthrough
Why one neighbour is an ancestor of the other. The keys a and b are adjacent in order. By the lemma in the article, a is an ancestor of b if a has the highest priority among the keys from a to b, and there are no other keys between them, so it is simply a comparison of the priorities of a and b: whichever is higher is the ancestor. It also works without the lemma: there is only one empty link between a and b in a search tree, the right link of a or the left link of b, and the search path to it passes through both.
How many nodes the cut passes. At each node a cut along m chooses the same direction as a search for m: right if the key is less than m, left if not. A search for a key between a and b passes through both and ends at an empty link under the deeper of them. So the cut passes all the nodes of the path from the root to the deeper neighbour, exactly as many as its depth. If the meridian is left of all keys, there is no neighbour a, and the path ends under the leftmost node b; on the right, the mirror image.
Implementation. Sort the nodes by key and build the tree with a stack: a new node pops nodes with lower priority off the stack, and the last one popped becomes its left child, while it becomes the right child of the top of the stack. The root is the bottom of the stack. Compute the depths with a traversal using an explicit stack: a stick of 10⁵ nodes will not get through Python recursion. For each meridian bisect_left finds the place i where keys[i − 1] < m ≤ keys[i], and the answer is max(depth of keys[i − 1], depth of keys[i]).
On towns with population as priority, a cut along the prime meridian passes 23 nodes, and along the 180th meridian, beyond which there are no keys, 12; in the tree with latitude as priority the cuts are longer, because the tree itself is higher. In the stick of the fifth test a cut at the left edge passes all 10⁵ nodes.
5+Solution
6Complexity
Sorting is O(n log n), building and depths O(n), each meridian O(log n) for the binary search. Memory O(n).
7Common mistakes
- An honest cut for each query. Correct, but on the stick of the fifth test that is 10⁵ queries of 5·10⁴ steps on average, 5·10⁹ steps.
- The depth of one neighbour. The path ends under the deeper of the two, not under the one on the left.
- Inserting one by one. Building the tree by insertions with rotations is O(n) per insertion on the same stick.
- The boundary. A key equal to the meridian goes east: you need the first key not less than m, not the first greater.
Algorithms behind it
O(log n) on average for search, insert, delete, split and merge
1 problem
DS
Technique
Monotonic stack
A stack with ordered values: the nearest greater element and the largest rectangle in O(n).
O(n)
2 problems