Parallel binary search
Parallel binary search
Example Problem
You are given people and lands. Each land () has an owner (), and each person has a target resource level .
Parallel binary search
You are given people and lands. Each land () has an owner (), and each person has a target resource level .
events occur sequentially. Each event is given by a triple and means that lands from to generate resources.
Note that can be greater than , since the lands are arranged in a circle.
If a person owns lands on the segment , then they receive resources.
For each person, you need to determine after which event they will reach their target resource level. If this is impossible, output -1.
For each person , you can solve the problem separately using binary search on the answer.
Let can(x, m) = true if person can accumulate the required amount of resources after the first events.
To answer can(x, m), you need to be able to quickly add the first events and compute the contribution over that person's lands. This can be done using a Fenwick tree or a segment tree.
Idea for one person:
The problem here is that we add and remove the same events many times.
Main idea: answer the binary search for all people at once.
The function can(x, m) itself works fast enough, and what is slow is the repeated adding/removing of events.
Therefore, we split people by the answer at the midpoint and recursively process the groups.
This way we reduce the number of repeated updates and get good asymptotics.
The same idea can be written iteratively.
For each person we store the binary search boundaries:
tl[x] — left boundarytr[x] — right boundaryInitially for all:
tl[x] = 0tr[x] = K + 1On each iteration we group people by their midpoint (tl[x] + tr[x]) / 2, sequentially add events and check can(x, m).
int solve(int x) {
int l = 0, r = K + 1;
while (l < r) {
int m = (l + r) / 2;
add_updates(1, m);
if (can(x, m)) {
r = m;
} else {
l = m + 1;
}
remove_updates(1, m);
}
if (l == K + 1) return -1;
return l;
}
void solve(int l, int r, vector<int> can_x) {
if (can_x.empty()) {
return;
} else if (l == r) {
for (int x: can_x) {
if (l == K + 1) {
res[x] = -1;
} else {
res[x] = l;
}
}
return;
}
int m = (l + r) / 2;
add_updates(l, m);
vector<int> can_l, can_r;
for (int x: can_x) {
if (can(x, m)) {
can_l.push_back(x);
} else {
can_r.push_back(x);
}
}
remove_updates(l, m);
solve(l, m, can_l);
solve(m + 1, r, can_r);
}
void solve() {
for (int i = 1; i <= n; i++) {
tl[i] = 0;
tr[i] = K + 1;
}
for (int it = 0; it < LOG_K; it++) {
for (int i = 0; i <= K; i++) {
query[i].clear();
}
for (int i = 1; i <= n; i++) {
query[(tl[i] + tr[i]) / 2].push_back(i);
}
for (int m = 0; m <= K; m++) {
if (m > 0) {
add_updates(m, m);
}
for (int x : query[m]) {
if (can(x, m)) {
tr[x] = m;
} else {
tl[x] = m + 1;
}
}
}
remove_updates(1, K);
}
}