1452. How Many Were Playing at That Second

n players each play once. Player i is online over the HALF-OPEN stretch [a, b) with a < b: online from second a up to but NOT including second b. Then q questions arrive, each a single second x.

For each question, print how many players are online at second x, one answer per line, in the ORDER THE QUESTIONS WERE ASKED.

players [1,5) [2,6) [8,9) [3,4), asked 1, 3, 5, 8, 9 -> 1 / 3 / 1 / 1 / 0 players [1,3) [3,5), asked 3 -> 1 players [5,6), asked 4, 5, 6 -> 0 / 1 / 0

The second line is the endpoint rule. At second 3 the first player has already gone, because [1,3) stops short of 3, and the second has just arrived. One player, not two and not zero. The third line says the same thing from the other side: the start second counts, the end second does not.

## What most people try first

Scanning every player for every question. It is obviously correct and it is O(nq), which at n = q = 10^5 is 10^10 tests, ten billion of them.

The second reflex is a counter per second, filled once and then read in constant time. Seconds reach 10^9 in both directions, so the array cannot be built.

## Answer all the questions in one sweep

The questions do not have to be answered in the order they were asked. Sort them, sweep once, and put each answer back where it belongs:

events: (a, +1) and (b, -1) for each player; sort by coordinate sort the question indices by their second count = 0; j = 0 for each question index i, in sorted order of x = question[i]: while j < 2n and event[j].coordinate <= x: count += event[j].delta; j = j + 1 answer[i] = count print answer[0 .. q-1] in the original order

O((n + q) log(n + q)) for the two sorts and one linear pass. This is the OFFLINE pattern: the questions are all known in advance, so they can be reordered.

## Why <= x is the whole of the endpoint rule

The events consumed are those at coordinates at or before x. A start at x is consumed, so the player counts. An end at x is also consumed, so that player does not count. Together that is exactly "online at x when a <= x < b". Changing <= to < reads the intervals as (a, b] instead, and every answer at a shared endpoint changes.

Because all events at or before x are consumed before the count is read, the tie-break between a +1 and a -1 at the same coordinate does not affect the answers. It does matter in problem 1448, where the count is read after each single event.

## The boundary that breaks a careless implementation

The answers must be printed in the ORDER ASKED, not in sorted order. Carrying the original index alongside each question is the whole of it, and forgetting is the most common way to fail this problem with an otherwise correct sweep.

A question before every start, or after every end, must answer 0 rather than running off either end of the event list.

## Overflow

Answers are at most n = 10^5 and coordinates at most 10^9 in magnitude, both inside the 2147483647 a signed 32 bit integer holds. Nothing accumulates. Build the output in one string: 10^5 separate prints is slow enough to matter on its own.

## Related

Problem 934 answers a point query too, but asks for the LENGTH of the shortest interval containing the point, which needs a structure rather than a counter. Problem 1462 asks which interval covering the point arrived LAST. Problem 1448 asks for the largest count over all points rather than the count at given ones.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `-10^9 ≤ a < b ≤ 10^9` - `-10^9 ≤ x ≤ 10^9` - each player is online over the half-open stretch `[a, b)`, so second `a` counts and second `b` does not