1462. Which Stroke Is on Top

A long wall is painted with n strokes, applied in the order given. Stroke i (numbered from 1) covers the HALF-OPEN stretch [a, b) with a < b, and a later stroke paints OVER an earlier one wherever they overlap.

Then q questions arrive, each a single point x. For each, print the number of the stroke visible at x, or 0 if the wall is bare there. Answer in the ORDER THE QUESTIONS WERE ASKED.

strokes [0,10) [2,5) [7,9), asked 1, 3, 6, 8 -> 1 / 2 / 1 / 3 strokes [1,3) [3,5), asked 2, 3, 5 -> 1 / 2 / 0 strokes [7,8), asked 6, 7, 8 -> 0 / 1 / 0

The second line is the endpoint rule. The two strokes merely TOUCH: stroke 1 covers [1,3) and stops just short of 3, and stroke 2 covers [3,5) and starts there. So at point 3 the visible stroke is 2, not 1, and at point 5 the wall is bare because [3,5) does not include 5.

## What most people try first

For each question, scanning all n strokes backwards and stopping at the first that covers the point. Correct, and O(nq): 10^10 tests at the limits.

The second reflex is to simulate the painting on an array indexed by point. Coordinates run to 10^9 in both directions, so the array would need 2 * 10^9 entries.

The third, and the interesting failure, is to sweep left to right keeping "the stroke covering the current point with the largest number". That needs, at every moment, the maximum over a CHANGING set, and a running maximum cannot be undone when the stroke holding it expires. It is the same reason problem 914 needs a heap where problem 1453 needs only a counter: maximum has no inverse and addition does.

## Compress the coordinates, then tag ranges with a maximum

Only 2n + q coordinates are ever mentioned, so replace each by its position in the sorted list of distinct values. Ranks preserve order, so a <= x < b becomes rank(a) <= rank(x) < rank(b), and the axis shrinks to at most 3 * 10^5 slots.

Over that axis, build a segment tree that holds one TAG per node and supports:

tag a range: for each of the O(log) nodes exactly covering [l, r), tag[node] = max(tag[node], value) no pushing down query a point: walk from the root down to the leaf, taking the maximum of every tag on the way

Apply the strokes in order, tagging [rank(a), rank(b)) with the stroke number, then answer each question with one root-to-leaf walk.

O((n + q) log(n + q)).

## Why no pushing down is needed

A tag at a node means "every point under this node is covered by at least this stroke number". The answer at a point is the largest stroke covering it, which is the largest tag on any node whose range contains the point, and those nodes are exactly the ones on the root-to-leaf path. So the query collects every relevant tag without the tags ever having to be moved.

That is the whole trick, and it is what makes this tree about ten lines rather than forty: laziness is usually about deferring work until a child is READ, and here the read already visits every ancestor.

Applying the strokes in increasing order is not required either, since the combining operation is a maximum and maximum does not care about order. It is simply the natural way to read them.

## The boundary that breaks a careless implementation

The range tagged is [rank(a), rank(b)), half-open in rank space, which works only because every query coordinate is included in the compression. If a question point were left out, its rank would fall between two others and the comparison rank(a) <= rank(x) < rank(b) would no longer mean a <= x < b.

And the answers must come out in the order asked, not in sorted order, so each question carries its original index if the questions are reordered at all.

## Overflow

Stroke numbers reach 10^5 and coordinates 10^9, both far inside the 2147483647 a signed 32 bit integer holds. Nothing is summed. The tree needs about 2^20 entries at the limits, which is four megabytes at four bytes each.

## Related

Problem 934 answers point queries about intervals too, but asks for the LENGTH of the shortest interval containing the point, which is a minimum over a changing set and is answered offline with a heap. Problem 1452 asks how MANY intervals cover the point, which is additive and needs only a running count. The three together are a small catalogue of what the combining operation costs you.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `-10^9 ≤ a < b ≤ 10^9` - `-10^9 ≤ x ≤ 10^9` - each stroke covers the half-open stretch `[a, b)`, so point `a` is covered and point `b` is not - strokes are applied in the order given, and a later stroke hides an earlier one where they overlap