Parallel Binary Search

Mỗi vòng một lượt quét

Đ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, mẫu chặt nhị phân quen thuộc giữ lo, hi, res: thử mid, đúng thì ghi res = mid và sang trái, sai thì sang phải.

Chặt riêng: 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 định nghĩa của đề: ở đây sau bước $t$ trạng thái chứa đúng $t$ cạnh đầu.

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;
using 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';
}

Input6 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.

Trạng thái là tổng tích lũy

Điều kiện không nhất thiết là liên thông. Khi mỗi bước thời gian cộng thêm một lượng không âm và 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ần đọc nhiều điểm; tổng số điểm đọc trong một vòng vẫn là tổ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: vừa nhanh hơn, vừa 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;
using 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";
    }
}

Input5 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.

Hỏi thông tin của 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 bước thời gian là cạnh sắp theo trọng số, “thời điểm” thành “ngưỡng”: điều kiện đúng ở ngưỡng $W$ thì đúng ở mọi ngưỡng lớn hơn. Nếu nhiều cạnh cùng trọng số, cho mỗi bước thời gian là cả nhóm cạnh bằng nhau, để không kiểm giữa chừng một nhóm. Thông tin cần in kèm đáp án (như kích thước) được ghi lại ngay lúc kiểm đúng: lần ghi cuối cùng ứng với res cuối cùng.

Ví dụPhủ Đủ Đỉnh

Đề. Đồ thị liên thông $N, M \le 10^5$, cạnh đánh số theo input. Truy vấn $(x, y, z)$: tìm $t$ nhỏ nhất để trong đồ thị gồm $t$ cạnh đầu, tổng số đỉnh của thành phần chứa $x$ và thành phần chứa $y$ (một lần nếu trùng) ít nhất $z$.

Lời giải. Thêm cạnh chỉ làm thành phần lớn lên, nên số đỉnh phủ được bởi hai thành phần chứa $x$, $y$ không giảm theo $t$: chặt nhị phân song song trên $[1, M]$, khung giống hệt ví dụ đầu. Với $t = M$ đồ thị liên thông, số đỉnh là $N \ge z$, nên mọi truy vấn đều có đáp án.

Bước 1: DSU giữ kích thước. Hợp theo kích thước, cộng sz vào gốc mới.

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];
}

Bước 2: kiểm. Hai đỉnh cùng thành phần thì chỉ đếm một lần; khác thì cộng hai kích thước.

int a = find(qx[i]), b = find(qy[i]);
int c = a == b ? sz[a] : sz[a] + sz[b];
if (c >= qz[i]) res[i] = t, hi[i] = t - 1;
else lo[i] = t + 1;

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

const int N = 1e5 + 5;
int n, m, q, eu[N], ev[N], qx[N], qy[N], qz[N], lo[N], hi[N], res[N], par[N], sz[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];
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> qx[i] >> qy[i] >> qz[i];
        lo[i] = 1, hi[i] = m;
    }
    while (true) {
        bool any = 0;
        for (int t = 1; 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, sz[u] = 1;
        for (int t = 1; t <= m; t++) {
            unite(eu[t], ev[t]);
            for (int i : bucket[t]) {
                int a = find(qx[i]), b = find(qy[i]);
                int c = a == b ? sz[a] : sz[a] + sz[b];
                if (c >= qz[i]) res[i] = t, hi[i] = t - 1;
                else lo[i] = t + 1;
            }
        }
    }
    for (int i = 1; i <= q; i++) cout << res[i] << '\n';
}

+11 dòngInput6 6
1 2
3 4
2 3
5 6
4 5
1 6
3
1 5 4
1 6 6
2 4 3

Output3
4
1

Mỗi vòng $O((M + Q)\,\alpha(N))$, khoảng 17 vò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;
using 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òngInput7 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 hỗ trợ 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.

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;
using 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';
}

Input7 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)$.