Parallel Binary Search

Resources

Tutorial

This technique is usually used when we can solve a single query by doing linear or binary search on monotonic function.

The trick is doing it offline, sort queries by their median (initially $l$, $r$ will be the binary search values), do linear search, whenever you find a query its median in same as your position in linear search, check the monotonic function, and do same as binary search (edit either $l$ or $r$).

You will need to do the linear search $O(\log_2{N})$ times, so $l = r$.

Usually the complexity would be: $O((N+Q) \cdot \log_2{(N+Q)}^2)$

Solution - New Roads Queries

We can see that connectivity of the nodes is a monotonic function.

Now let's use parallel binary search:

When sweeping through the array of edges, union them in the DSU.

Whenever there is a query with median = $i$, if the two nodes where connected in DSU, it means the answer is $\leq i$ ($r = i$), otherwise it means $\gt i$ ($l = i+1$).

Total Complexity: $O((N+Q) \cdot \log_2(N+Q)^2 \cdot \alpha{(N)})$, $\alpha{(N)}$ is for the DSU.

Implementation - New Roads Queries

Copy
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 1;

struct DSU {
	int cnt[N], par[N];
	void Init(int sz) {
		for (int i = 0; i <= sz; i++) par[i] = i, cnt[i] = 1;
	}

Problems