Parallel Binary Search

Resources

Solution - New Roads Queries

Let's think about how to use binary to answer single query. We can see that connvectivity of the nodes is a monotonic function.

Now let's use parallel binary search:

First, sort the queries by median.

Then sweep through the array of edges and union them in the DSU, whenevery there is a query with median = $i$, if the two nodes where connected in DSU, it means the answer is $\leq i$, otherwise it means $\gt i$.

Complexity:

We need to do the sweep $O(\log_2{N})$ times, same as binary search. Sorting the queries by median is $O(Q \cdot \log_2{Q})$ And $O(\alpha(N))$ for the DSU

Total Complexity: $O((N + Q) \cdot \log_2(N+Q)^2 \cdot \alpha(N))$

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