Parallel Binary Search

Quét song song

Điều kiện kiểm $P_i(t)$ của truy vấn $i$ phải đơn điệu: sai, sai, …, đúng, đúng khi $t$ tăng. Đồ thị chỉ thêm cạnh là ví dụ chuẩn: đã liên thông thì mãi liên thông. Với một truy vấn, chặt nhị phân giữ lo, hi, res: thử mid, đúng thì ghi res = mid và sang trái, sai thì sang phải.

Chặt riêng từng truy vấn: mỗi lần thử phải dựng trạng thái sau mid bước từ đầu, $q$ truy vấn tốn $O(q \cdot m \log m)$. Chặt song song đảo vòng lặp:

1. Mỗi truy vấn còn lo <= hi bỏ chỉ số của nó vào giỏ bucket[mid].
2. Làm rỗng cấu trúc, quét $t = 0, 1, \dots, m$: áp dụng bước $t$, rồi kiểm mọi truy vấn trong bucket[t] và cập nhật cận của chúng.
3. Lặp tới khi không truy vấn nào còn khoảng.

Mỗi vòng tốn một lượt quét cộng $q$ lần kiểm; khoảng của mỗi truy vấn giảm một nửa nên có $\lceil \log_2(m + 1) \rceil$ vòng. Thứ tự “cập nhật rồi mới kiểm” phải khớp đề: sau bước $t$ trạng thái chứa đúng $t$ cạnh đầu.

Trong hình, mỗi hàng là một truy vấn. Thanh xanh là khoảng còn lại, chấm đỏ là điểm giữa được kiểm trong lượt quét, ô xanh lá là đáp án đã biết.

Ví dụNgày Kết Nối Đầu Tiên

Đề. $n$ đỉnh, ngày $i$ thêm cạnh thứ $i$ ($m \le 2 \cdot 10^5$). Mỗi truy vấn $(u, v)$ hỏi số ngày ít nhất để $u, v$ liên thông (ngày 0 là chưa thêm cạnh), hoặc $-1$.

Lời giải. Với một truy vấn, “$u$, $v$ liên thông sau $t$ ngày” đúng thì đúng với mọi ngày sau, nên đáp án chặt nhị phân được trên $[0, m]$. Chặt riêng từng truy vấn thì mỗi lần kiểm phải dựng lại DSU. Chặt song song: mỗi vòng, mọi truy vấn bỏ vào giỏ ứng với điểm giữa của nó; dựng DSU một lần, thêm cạnh theo ngày, tới ngày $t$ thì kiểm hết các truy vấn trong giỏ $t$. Mỗi vòng thu hẹp mọi khoảng còn một nửa.

Bước 1: khoảng chặt. lo[i], hi[i] là khoảng còn chặt của truy vấn $i$; lo > hi là đã xong. res = -1 sẵn cho truy vấn không bao giờ nối được.

lo[i] = 0, hi[i] = m, res[i] = -1;

Bước 2: chia giỏ. Đầu mỗi vòng xóa giỏ, bỏ từng truy vấn còn chặt vào giỏ (lo + hi) / 2. Không còn truy vấn nào thì dừng.

for (int t = 0; t <= m; t++) bucket[t].clear();
for (int i = 1; i <= q; i++)
    if (lo[i] <= hi[i]) {
        bucket[(lo[i] + hi[i]) / 2].push_back(i);
        any = 1;
    }
if (!any) break;

Bước 3: quét theo ngày. Ngày 0 chưa có cạnh; ngày $t > 0$ thêm cạnh $t$. Rồi kiểm các truy vấn trong giỏ $t$: liên thông thì ghi res = t và chặt nửa trái, ngược lại chặt nửa phải.

for (int u = 1; u <= n; u++) par[u] = u;
for (int t = 0; t <= m; t++) {
    if (t) par[find(eu[t])] = find(ev[t]);
    for (int i : bucket[t]) {
        if (find(qu[i]) == find(qv[i])) res[i] = t, hi[i] = t - 1;
        else lo[i] = t + 1;
    }
}

find nén nửa đường (par[u] = par[par[u]]), không cần đệ quy.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 2e5 + 5;
int n, m, q, eu[N], ev[N], qu[N], qv[N], lo[N], hi[N], res[N], par[N];
vector<int> bucket[N];

int find(int u) {
    while (par[u] != u) u = par[u] = par[par[u]];
    return u;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) cin >> eu[i] >> ev[i];
    for (int i = 1; i <= q; i++) {
        cin >> qu[i] >> qv[i];
        lo[i] = 0, hi[i] = m, res[i] = -1;
    }
    while (true) {
        bool any = 0;
        for (int t = 0; t <= m; t++) bucket[t].clear();
        for (int i = 1; i <= q; i++)
            if (lo[i] <= hi[i]) {
                bucket[(lo[i] + hi[i]) / 2].push_back(i);
                any = 1;
            }
        if (!any) break;
        for (int u = 1; u <= n; u++) par[u] = u;
        for (int t = 0; t <= m; t++) {
            if (t) par[find(eu[t])] = find(ev[t]);
            for (int i : bucket[t]) {
                if (find(qu[i]) == find(qv[i])) res[i] = t, hi[i] = t - 1;
                else lo[i] = t + 1;
            }
        }
    }
    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

ChạyInput6 4 4
1 2
3 4
2 3
1 4
1 4
1 6
2 2
3 1

Output3
-1
0
3

Mỗi vòng $O((m + q)\,\alpha(n))$, khoảng $\log_2 m + 1 = 19$ vòng.

Tổng tích lũy

Điều kiện không nhất thiết là liên thông. Mỗi bước thời gian cộng thêm một lượng không âm, truy vấn hỏi “tổng đã đạt ngưỡng chưa”: điều kiện cũng đơn điệu. Trạng thái dựng bằng Fenwick: mỗi vòng xóa cây, áp lần lượt các bước, kiểm truy vấn trong giỏ.

Một truy vấn có thể đọc nhiều điểm, nhưng tổng số điểm đọc trong một vòng vẫn bằng kích thước dữ liệu, nên mỗi vòng $O((m + k) \log m)$. Khi cộng dồn, dừng sớm ngay khi đạt ngưỡng: nhanh hơn và tránh tràn số.

Ví dụMưa Thiên Thạch

Đề. Vòng tròn $m$ khu vực, khu $i$ thuộc quốc gia $o_i$; quốc gia $i$ cần $p_i$ mẫu. Sự kiện $j$ cộng $a_j$ mẫu cho mỗi khu trên cung $l..r$ (có thể vòng qua $m$). Với mỗi quốc gia, in sự kiện sớm nhất mà tổng mẫu của nó đạt $p_i$, hoặc NIE. Mọi giới hạn tới $3 \cdot 10^5$.

Lời giải. Tổng mẫu của một quốc gia chỉ tăng theo sự kiện, nên “đã đạt $p_i$ sau sự kiện $j$” là điều kiện đơn điệu: chặt nhị phân song song trên chỉ số sự kiện, khung vòng lặp như ví dụ trước. Khác ở trạng thái: lượng mẫu ở mỗi khu, cập nhật bằng cộng đoạn.

Bước 1: cộng đoạn, đọc điểm. Fenwick trên mảng hiệu: range(l, r, v) cộng v ở ô $l$ và trừ ở ô $r + 1$; get(p) là tổng tiền tố, tức lượng ở khu $p$.

void range(int l, int r, ll v) {
    add(l, v);
    add(r + 1, -v);
}

Bước 2: cung vòng. Cung vòng qua $m$ tách thành hai đoạn $l..m$ và $1..r$.

if (el[j] <= er[j]) range(el[j], er[j], ea[j]);
else range(el[j], m, ea[j]), range(1, er[j], ea[j]);

Bước 3: kiểm một quốc gia. pos[o] là danh sách khu của quốc gia $o$; tổng độ dài mọi danh sách là $m$, nên mỗi vòng đọc tối đa $m$ điểm. Dừng sớm khi đã đủ: vừa nhanh hơn, vừa tránh tràn, vì tổng thật có thể tới $3 \cdot 10^5 \cdot 3 \cdot 10^5 \cdot 10^9$.

ll got = 0;
for (int p : pos[i]) {
    got += get(p);
    if (got >= need[i]) break;
}
if (got >= need[i]) res[i] = j, hi[i] = j - 1;
else lo[i] = j + 1;

bit xóa đầu mỗi vòng; res = 0 là không bao giờ đủ, in NIE.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 3e5 + 5;
int n, m, k, el[N], er[N], lo[N], hi[N], res[N];
ll need[N], ea[N], bit[N];
vector<int> pos[N], bucket[N];

void add(int i, ll v) {
    for (; i <= m; i += i & -i) bit[i] += v;
}

ll get(int i) {
    ll s = 0;
    for (; i; i -= i & -i) s += bit[i];
    return s;
}

void range(int l, int r, ll v) {
    add(l, v);
    add(r + 1, -v);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int o;
        cin >> o;
        pos[o].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> need[i];
    cin >> k;
    for (int j = 1; j <= k; j++) cin >> el[j] >> er[j] >> ea[j];
    for (int i = 1; i <= n; i++) lo[i] = 1, hi[i] = k, res[i] = 0;
    while (true) {
        bool any = 0;
        for (int j = 1; j <= k; j++) bucket[j].clear();
        for (int i = 1; i <= n; i++)
            if (lo[i] <= hi[i]) {
                bucket[(lo[i] + hi[i]) / 2].push_back(i);
                any = 1;
            }
        if (!any) break;
        memset(bit, 0, sizeof(bit));
        for (int j = 1; j <= k; j++) {
            if (el[j] <= er[j]) range(el[j], er[j], ea[j]);
            else range(el[j], m, ea[j]), range(1, er[j], ea[j]);
            for (int i : bucket[j]) {
                ll got = 0;
                for (int p : pos[i]) {
                    got += get(p);
                    if (got >= need[i]) break;
                }
                if (got >= need[i]) res[i] = j, hi[i] = j - 1;
                else lo[i] = j + 1;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (res[i]) cout << res[i] << '\n';
        else cout << "NIE\n";
    }
}

ChạyInput5 7
1 2 1 3 4 2 3
5 6 10 4 1
4
6 2 2
3 5 3
1 7 1
4 4 10

Output2
3
4
3
NIE

Mỗi vòng $O((k + m) \log m)$, khoảng 19 vòng.

Ngưỡng và thành phần

DSU giữ thêm kích thước thành phần thì điều kiện có thể là “số đỉnh phủ được đạt $z$”.

Khi các cạnh sắp theo trọng số, “thời điểm” thành “ngưỡng”: đúng ở ngưỡng $W$ thì đúng ở mọi ngưỡng lớn hơn. Nhiều cạnh cùng trọng số thì mỗi bước là cả nhóm cạnh bằng nhau, để không kiểm giữa chừng một nhóm.

Thông tin in kèm đáp án (như kích thước) được ghi ngay lúc kiểm đúng; lần ghi cuối cùng ứng với res cuối cùng.

Ví dụNgưỡng Liên Thông

Đề. Đồ thị $n, m \le 10^5$ có trọng số. Với truy vấn $(x, y)$, tìm $W$ nhỏ nhất để chỉ giữ cạnh trọng số không vượt $W$ thì $x, y$ liên thông, và in kèm kích thước thành phần đó sau khi thêm mọi cạnh trọng số không vượt $W$; không được thì $-1$.

Lời giải. Sắp cạnh theo trọng số, coi “thời điểm” là ngưỡng. Các cạnh cùng trọng số phải được thêm cùng lúc, vì đề hỏi kích thước sau khi thêm mọi cạnh không vượt $W$; nên gom thành $G$ nhóm trọng số bằng nhau và chặt nhị phân song song trên chỉ số nhóm $[1, G]$.

Bước 1: sắp và gom nhóm. e[i] là cặp (trọng số, chỉ số cạnh) để sắp theo trọng số mà vẫn nhớ hai đầu mút. gw[g] là trọng số của nhóm $g$, gend[g] là chỉ số cạnh cuối của nhóm trong mảng đã sắp.

sort(e + 1, e + m + 1);
for (int i = 1; i <= m; i++) {
    if (i == 1 || e[i].first != e[i - 1].first) gw[++G] = e[i].first;
    gend[G] = i;
}

Bước 2: quét theo nhóm. Ở nhóm $g$, thêm các cạnh từ gend[g - 1] + 1 tới gend[g], rồi kiểm giỏ. Kiểm đúng thì ghi luôn kích thước thành phần. Mỗi lần kiểm đúng về sau chỉ xảy ra ở ngưỡng nhỏ hơn và ghi đè, nên giá trị cuối cùng ứng với ngưỡng nhỏ nhất.

for (int g = 1; g <= G; g++) {
    for (int j = gend[g - 1] + 1; j <= gend[g]; j++) unite(eu[e[j].second], ev[e[j].second]);
    for (int i : bucket[g]) {
        int a = find(qx[i]);
        if (a == find(qy[i])) res[i] = g, ans[i] = sz[a], hi[i] = g - 1;
        else lo[i] = g + 1;
    }
}

res = 0 là không bao giờ nối được, in $-1$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5;
int n, m, q, G, eu[N], ev[N], qx[N], qy[N], lo[N], hi[N], res[N], ans[N], par[N], sz[N], gend[N], gw[N];
pair<int, int> e[N];
vector<int> bucket[N];

int find(int u) {
    while (par[u] != u) u = par[u] = par[par[u]];
    return u;
}

void unite(int a, int b) {
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i] >> e[i].first;
        e[i].second = i;
    }
    sort(e + 1, e + m + 1);
    for (int i = 1; i <= m; i++) {
        if (i == 1 || e[i].first != e[i - 1].first) gw[++G] = e[i].first;
        gend[G] = i;
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> qx[i] >> qy[i];
        lo[i] = 1, hi[i] = G, res[i] = 0;
    }
    while (true) {
        bool any = 0;
        for (int g = 1; g <= G; g++) bucket[g].clear();
        for (int i = 1; i <= q; i++)
            if (lo[i] <= hi[i]) {
                bucket[(lo[i] + hi[i]) / 2].push_back(i);
                any = 1;
            }
        if (!any) break;
        for (int u = 1; u <= n; u++) par[u] = u, sz[u] = 1;
        for (int g = 1; g <= G; g++) {
            for (int j = gend[g - 1] + 1; j <= gend[g]; j++) unite(eu[e[j].second], ev[e[j].second]);
            for (int i : bucket[g]) {
                int a = find(qx[i]);
                if (a == find(qy[i])) res[i] = g, ans[i] = sz[a], hi[i] = g - 1;
                else lo[i] = g + 1;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (res[i]) cout << gw[res[i]] << ' ' << ans[i] << '\n';
        else cout << -1 << '\n';
    }
}

+13 dòngChạyInput7 6
1 2 4
2 3 7
3 4 7
5 6 2
4 5 10
2 6 10
5
1 3
1 6
5 6
1 5
1 7

Output7 4
10 6
2 2
10 6
-1

$O(m \log m)$ để sắp, mỗi vòng $O((m + q)\,\alpha(n))$.

Chặt nhị phân tổng thể

Bài “phần tử nhỏ thứ $k$ trong đoạn $[l, r]$” cũng là chặt nhị phân: đáp án là giá trị $x$ nhỏ nhất mà đoạn có ít nhất $k$ phần tử không vượt $x$. Thay vì chạy theo vòng, ta đệ quy trên miền giá trị. Hàm solve(lo, hi, danh sách) nhận các truy vấn có đáp án trong $[lo, hi]$ cùng các phần tử có giá trị trong $[lo, hi]$:

1. Lấy mid. Thêm vào Fenwick theo vị trí mọi phần tử có giá trị không vượt mid.
2. Với mỗi truy vấn, đếm $c$ phần tử như vậy trong $[l, r]$. Nếu $k \le c$, đáp án ở nửa trái; ngược lại trừ $k$ đi $c$ và đưa sang nửa phải, vì $c$ phần tử nhỏ đó đã được tính.
3. Xóa các phần tử vừa thêm, chia danh sách làm hai, đệ quy hai nửa.

Mỗi phần tử và truy vấn xuất hiện ở một nhánh trên mỗi tầng, có $\log V$ tầng, nên tổng $O((n + q) \log V \log n)$. Muốn có cập nhật, coi mỗi phép gán là “xóa giá trị cũ, thêm giá trị mới” và giữ mọi thao tác theo thứ tự thời gian trong danh sách; khung đệ quy không đổi.

Mỗi lần gọi đệ quy ta chia danh sách làm hai. Tạo hai vector mới ở mỗi lần gọi là cách dễ viết, nhưng hằng số phải trả:

Dùng một mảng tạm chung (nửa trái ghi đè ngay tại chỗ, nửa phải qua mảng tạm rồi chép về) nhanh hơn khoảng 1,6 lần. Quy tắc: đệ quy chia đôi dữ liệu thì tránh cấp phát trong mỗi lần gọi.

Ví dụTrung Vị Đoạn

Đề. Mảng $n \le 10^5$ phần tử, giá trị tới $10^5$. Mỗi truy vấn $[l, r]$ hỏi phần tử thứ $\lfloor (len + 1)/2 \rfloor$ khi sắp tăng dần đoạn đó.

Lời giải. Trung vị là phần tử thứ $k = \lfloor (len + 1)/2 \rfloor = (r - l + 2)/2$ của đoạn. Chặt nhị phân tổng thể trên miền giá trị $[1, 10^5]$: solve(lo, hi, …) nhận các phần tử có giá trị trong $[lo, hi]$ cùng các truy vấn có đáp án trong $[lo, hi]$. Đưa các phần tử $\le mid$ vào Fenwick theo vị trí; mỗi truy vấn đếm $c$ phần tử như vậy trong đoạn của nó. $k \le c$ thì đáp án $\le mid$; ngược lại đáp án $> mid$ và là phần tử thứ $k - c$ trong số các phần tử $> mid$.

Bước 1: một mảng chung. id[L..R] chứa cả phần tử (số $\le n$) lẫn truy vấn (số $n + j$). Ban đầu mọi phần tử đứng trước mọi truy vấn.

for (int i = 1; i <= n; i++) cin >> a[i], id[i] = i;
for (int j = 1; j <= q; j++) {
    cin >> ql[j] >> qr[j];
    qk[j] = (qr[j] - ql[j] + 2) / 2;
    id[n + j] = n + j;
}

Bước 2: chia hai nhóm. Phần tử $\le mid$ vào Fenwick và sang trái, còn lại sang phải. Truy vấn đếm c rồi sang trái, hoặc trừ qk[j] đi c và sang phải. Vì phần tử đứng trước truy vấn, lúc một truy vấn đếm thì mọi phần tử $\le mid$ của đoạn đã vào Fenwick.

for (int i = L; i <= R; i++) {
    int x = id[i];
    if (x <= n) {
        if (a[x] <= mid) add(x, 1), lf.push_back(x);
        else rt.push_back(x);
    } else {
        int j = x - n, c = get(qr[j]) - get(ql[j] - 1);
        if (qk[j] <= c) lf.push_back(x);
        else qk[j] -= c, rt.push_back(x);
    }
}

Bước 3: dọn và đệ quy. Trừ lại đúng các phần tử đã thêm để Fenwick về 0. lf, rt giữ nguyên thứ tự tương đối, nên trong mỗi nhóm con phần tử vẫn đứng trước truy vấn.

for (int x : lf)
    if (x <= n) add(x, -1);
int p = L;
for (int x : lf) id[p++] = x;
int M = p - 1;
for (int x : rt) id[p++] = x;
solve(lo, mid, L, M);
solve(mid + 1, hi, M + 1, R);

Khi lo == hi, mọi truy vấn còn lại có đáp án là lo.

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5 + 5;
int n, q, a[N], ql[N], qr[N], qk[N], ans[N], bit[N], id[2 * N];

void add(int i, int v) {
    for (; i <= n; i += i & -i) bit[i] += v;
}

int get(int i) {
    int s = 0;
    for (; i; i -= i & -i) s += bit[i];
    return s;
}

void solve(int lo, int hi, int L, int R) {
    if (L > R) return;
    if (lo == hi) {
        for (int i = L; i <= R; i++)
            if (id[i] > n) ans[id[i] - n] = lo;
        return;
    }
    int mid = (lo + hi) / 2;
    vector<int> lf, rt;
    for (int i = L; i <= R; i++) {
        int x = id[i];
        if (x <= n) {
            if (a[x] <= mid) add(x, 1), lf.push_back(x);
            else rt.push_back(x);
        } else {
            int j = x - n, c = get(qr[j]) - get(ql[j] - 1);
            if (qk[j] <= c) lf.push_back(x);
            else qk[j] -= c, rt.push_back(x);
        }
    }
    for (int x : lf)
        if (x <= n) add(x, -1);
    int p = L;
    for (int x : lf) id[p++] = x;
    int M = p - 1;
    for (int x : rt) id[p++] = x;
    solve(lo, mid, L, M);
    solve(mid + 1, hi, M + 1, R);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i], id[i] = i;
    for (int j = 1; j <= q; j++) {
        cin >> ql[j] >> qr[j];
        qk[j] = (qr[j] - ql[j] + 2) / 2;
        id[n + j] = n + j;
    }
    solve(1, 100000, 1, n + q);
    for (int j = 1; j <= q; j++) cout << ans[j] << '\n';
}

ChạyInput7 4
8 1 6 6 3 9 2
1 7
2 5
3 4
6 6

Output6
3
6
9

Đệ quy sâu $\log_2 10^5 \approx 17$ tầng, mỗi tầng mỗi phần tử và truy vấn chỉ ở một nhánh: $O((n + q) \log V \log n)$.