Parallel Binary Search

Each person $x$ has a target amount of resources $need_x$.

Each event is described by $(l_i, r_i, a_i)$ and means that every land in the segment $[l_i, r_i]$ generates $a_i$ resources. If the segment wraps around, then the lands are considered on a circle.

So if a person owns $t$ lands inside the affected segment, then this person gains $t \cdot a_i$ resources from that event.

For each person, we need to determine after which event they first reach their target amount. If they never reach it, the answer is -1.

Naive Solution

We can solve the problem independently for each person.

For one fixed person $x$, let $can(x, m)$ mean whether person $x$ can reach the required amount using only the first $m$ events.

This function is monotone:

• if can(x, m) is true, then can(x, m+1) is also true.

So for each person, we can binary search on the answer.

To evaluate can(x, m), we need to apply the first $m$ events. For that, we can use a Fenwick tree or a segment tree, together with helper functions like:

• add_updates(l, r)
• remove_updates(l, r)

Then we get the following solution for one person:

This works, but it is too slow, because the same updates are added and removed many times for different people.

Main Idea of Parallel Binary Search

The slow part is not checking can(x, m) itself, but repeatedly rebuilding the state for many different values of m.

The key observation is that many people ask questions about the same midpoint m.

So instead of running a separate binary search for each person, we process all people in parallel:

• group together all people whose current midpoint is the same;
• apply updates only once up to that midpoint;
• answer all those checks together.

This is called parallel binary search.

Recursive Version

We write a recursive function:

which means that the answer for every person in people lies in the interval $[l, r]$.

If l == r, then the answer for all these people is already fixed.

Otherwise:

1. let $m = \left\lfloor \frac{l+r}{2} \right\rfloor$
2. apply all events from l to m;
3. split the people into two groups:
   • those for whom can(x, m) is true go to the left half;
   • the others go to the right half;
4. remove the updates;
5. recurse on both halves.

The advantage is that updates are reused across many people instead of being rebuilt from scratch for each person separately.

Iterative Version

The same idea can also be implemented iteratively.

For each person $x$, we maintain a current search range:

• tl[x] — left boundary;
• tr[x] — right boundary.

Initially, for every person:

• tl[x] = 0
• tr[x] = K + 1

Then we repeat the following process:

1. for each person, compute the current midpoint $mid_x = \left\lfloor \frac{tl[x] + tr[x]}{2} \right\rfloor$
2. group people by these midpoints;
3. sweep through events in increasing order of m, applying updates as we go;
4. whenever we reach midpoint m, answer all people assigned to this midpoint;
5. update their binary search ranges.