Parallel Binary Search

Resources

Solution - New Roads Queries

Let's think how to binary search a single query. It's clear that we can use DSU with linear search, but also we can do binary search with DSU in $O(N \cdot \log_2{N})$.

Now let's use parallel binary search: Sweep through the array, whenevery you find a query its median = $i$, you will shrink it either to left or right. You need to do the sweep $O(\log_2{N})$ times, so every query is processed. Total Complexity: $O((N + Q) \cdot \log_2{N})$

Implementation - New Roads Queries

Copy
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5 + 1;

int n, m, q;
vector<pii> edges;

Problems