Divide and Conquer

Chia, trị, gộp: lũy thừa nhanh

Một thuật toán chia để trị gồm ba việc.

• Chia (divide): đưa bài toán cỡ $n$ về vài bài con cùng dạng, cỡ nhỏ hơn.
• Trị (conquer): giải từng bài con bằng chính thuật toán đang viết, tức đệ quy. Bài đủ nhỏ thì giải thẳng; đó là điều kiện dừng.
• Gộp (combine): ghép lời giải các bài con thành lời giải của bài ban đầu.

Ví dụ ngắn nhất là lũy thừa nhanh (fast exponentiation): tính $x^n \bmod m$ với $n$ tới $10^{18}$. Nhân từng thừa số cần $n - 1$ phép nhân, không thể kịp. Nhưng $x^n = (x^{n/2})^2$ khi $n$ chẵn và $x^n = x \cdot (x^{(n-1)/2})^2$ khi $n$ lẻ. Chia là đổi $n$ thành $\lfloor n/2 \rfloor$; trị là tính $x^{\lfloor n/2 \rfloor}$ bằng đệ quy; gộp là bình phương kết quả và nhân thêm $x$ nếu $n$ lẻ; điều kiện dừng là $n = 0$, khi đó $x^0 = 1$.

Chạy tay với $x = 3$, $n = 13$. Các lời gọi đi xuống theo $13 \to 6 \to 3 \to 1 \to 0$, rồi kết quả đi ngược lên: $3^0 = 1$, $3^1 = 3$, $3^3 = 3 \cdot 3^2 = 27$, $3^6 = 27^2 = 729$, $3^{13} = 3 \cdot 729^2 = 1\,594\,323$. Chỉ 4 phép bình phương và 3 phép nhân thêm, thay cho 12 phép nhân; tổng quát là khoảng $2\log_2 n$ thay vì $n - 1$. Gọi $T(n)$ là thời gian chạy với số mũ $n$. Mỗi lời gọi làm $O(1)$ việc rồi gọi một lần với số mũ nửa, nên $T(n) = T(n/2) + O(1)$: có khoảng $\log_2 n$ lời gọi, tức $O(\log n)$.

Điểm mấu chốt là kết quả $x^{\lfloor n/2 \rfloor}$ được tính một lần rồi lưu vào biến: chia để trị chỉ có lợi khi các bài con độc lập và mỗi bài con được giải một lần. Nếu các bài con chồng lên nhau thì đệ quy trần giải đi giải lại cùng một bài; viết $F(n) = F(n-1) + F(n-2)$ thành hai lời gọi cho thời gian tăng theo cấp số nhân, và chỗ của kiểu bài đó là quy hoạch động (bài 12).

Ví dụLũy Thừa Rút Gọn

Đề. Cho ba số nguyên dương $A, B, C \le 2^{31} - 1$. In $A^B \bmod C$.

Lời giải. Lũy thừa nhanh đúng như trên, với một lời gọi đệ quy mỗi mức. Ba chi tiết: điều kiện dừng trả 1 % C để $C = 1$ vẫn cho 0; lấy A % C trước lần gọi đầu để mọi số đem nhân đều nhỏ hơn $C$; và vì $C < 2^{31}$ nên tích hai số dư nhỏ hơn $2^{62}$, vừa ll. $B$ tới $2 \cdot 10^9$ nên đệ quy chỉ sâu khoảng 31 mức. Với $C$ tới $10^{18}$ thì tích phải tính bằng __int128.

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

ll A, B, C;

ll power(ll x, ll n) {
    if (n == 0) return 1 % C;
    ll h = power(x, n / 2);
    ll res = h * h % C;
    if (n % 2 == 1) res = res * x % C;
    return res;
}

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

    cin >> A >> B >> C;
    cout << power(A % C, B) << '\n';
}

Input7 13 10

Output7

Cây đệ quy và độ phức tạp

Giả sử mỗi lời gọi cỡ $n$ sinh $a$ bài con cỡ $n/b$ và phần việc riêng của nó (chia cộng gộp) tốn $f(n)$. Khi đó thời gian chạy $T(n)$ thỏa hệ thức truy hồi

Cách giải thực dụng nhất là vẽ cây đệ quy và cộng chi phí theo từng mức. Mức $i$ có $a^i$ nút, mỗi nút cỡ $n/b^i$ nên cả mức tốn $a^i f(n/b^i)$; cây dừng ở mức $\log_b n$, số lần chia $n$ cho $b$ tới khi còn 1 (giống $\log_2 n$ ở bài 03, chỉ thay 2 bằng $b$). Với sắp xếp trộn, $a = b = 2$ và $f(n) = cn$ vì gộp hai nửa tốn $O(n)$: mức $i$ có $2^i$ nút cỡ $n/2^i$ nên tốn $cn$, mọi mức bằng nhau. Có $\log_2 n + 1$ mức, vậy $T(n) = O(n \log n)$.

Khi $f(n) = c\,n^k$, chi phí mức $i$ là $c\,n^k q^i$ với $q = a / b^k$, nên chi phí mỗi mức gấp $q$ lần mức ngay trên nó, và $T(n)$ là tổng của $\log_b n + 1$ mức như vậy. Có ba khả năng.

• $q < 1$: các mức giảm dần, tổng cỡ số hạng đầu, $T(n) = O(n^k)$. Việc ở gốc quyết định.
• $q = 1$: mọi mức bằng nhau, $T(n) = O(n^k \log n)$.
• $q > 1$: các mức tăng dần, tổng cỡ mức cuối, tức số lá của cây vì mỗi lá tốn $O(1)$. Chẳng hạn $a = 4$, $b = 2$: mỗi mức số nút gấp 4, có $\log_2 n$ mức nên có $4^{\log_2 n} = n^2$ lá và $T(n) = O(n^2)$. Tổng quát số lá là $n^{\log_b a}$. Việc ở các lá quyết định.

Đó là định lý thợ (master theorem) cho dạng hay gặp; bản đầy đủ cho $f$ tùy ý xem ở phần Đọc thêm. Các hệ thức sẽ gặp trong bài:

Cây chỉ đẹp như vậy khi các bài con co lại theo tỉ lệ. Nếu mỗi lần chỉ bớt một phần tử thì $T(n) = T(n-1) + O(n) = O(n^2)$ và cây sâu $n$ mức, có thể tràn ngăn xếp; đó là trường hợp xấu nhất của quicksort. Chia đôi theo chỉ số luôn cân bằng (chỉ sâu $\log_2 n \approx 18$ mức với $n = 2 \cdot 10^5$); chia theo giá trị quanh một pivot thì cân bằng tùy dữ liệu, vì thế mới cần pivot ngẫu nhiên.

Ví dụĐộ Sâu Theo Cực Đại

Đề. Cho một hoán vị $a_1, \dots, a_n$ ($n \le 100$, tối đa 100 test). Gắn nó với cây nhị phân: phần tử lớn nhất là gốc, phần bên trái nó tạo cây con trái, phần bên phải tạo cây con phải, theo cùng quy tắc. In độ sâu của từng phần tử theo thứ tự trong hoán vị, gốc có độ sâu 0.

Lời giải. Định nghĩa đã là một lời gọi đệ quy: trên đoạn $[l, r)$, tìm vị trí $p$ của số lớn nhất, gán độ sâu hiện tại cho $p$, rồi giải $[l, p)$ và $[p + 1, r)$ với độ sâu tăng 1; đoạn rỗng thì dừng. Điểm chia là vị trí số lớn nhất chứ không phải điểm giữa, nên cây không cân bằng: với hoán vị tăng dần, mỗi lần chỉ tách được một phần tử và $T(n) = T(n - 1) + O(n) = O(n^2)$, đúng trường hợp xấu đã nói. Với $n \le 100$ chuyện đó chẳng sao, nhưng với $n = 10^5$ thì cần cách khác (bài 17).

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

ll t, n, a[105], d[105];

void go(ll l, ll r, ll dep) {
    if (l >= r) return;
    ll p = l;
    for (ll i = l + 1; i < r; i++)
        if (a[i] > a[p]) p = i;
    d[p] = dep;
    go(l, p, dep + 1);
    go(p + 1, r, dep + 1);
}

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

    cin >> t;
    while (t--) {
        cin >> n;
        for (ll i = 0; i < n; i++) cin >> a[i];
        go(0, n, 0);
        for (ll i = 0; i < n; i++) cout << d[i] << ' ';
        cout << '\n';
    }
}

Input1
5
2 5 1 4 3

Output1 0 2 1 2

Sắp xếp trộn

Bài toán: sắp $n$ số tăng dần bằng sắp xếp trộn (merge sort). Gộp hai dãy đã sắp thành một dãy sắp chỉ cần một lượt duyệt, nên ta giao việc sắp mỗi nửa cho đệ quy.

Quy ước chỉ số của cả bài. Mọi đoạn trong đệ quy là đoạn nửa mở $[l, r)$, đánh số từ 0: gồm các vị trí $l, l+1, \dots, r-1$, độ dài $r - l$. Đặt $\mathrm{mid} = (l + r) / 2$ thì hai nửa $[l, \mathrm{mid})$ và $[\mathrm{mid}, r)$ không giao nhau, hợp lại đúng $[l, r)$, không phải cộng trừ 1 ở đâu cả. Đoạn dài 0 hoặc 1 đã sắp sẵn: điều kiện dừng là r - l <= 1.

Giả sử hai nửa đã tăng. Đặt hai con trỏ $i$, $j$ vào phần tử đầu chưa lấy của mỗi nửa. Phần tử nhỏ nhất trong mọi phần tử chưa lấy chắc chắn là một trong hai phần tử đó, nên mỗi bước ta so hai phần tử ấy, ghi cái nhỏ hơn vào mảng phụ rồi dịch con trỏ. Khi một nửa hết, chép nguyên phần còn lại của nửa kia. Ví dụ gộp $(2, 5)$ với $(1, 7)$: lấy $1$, rồi $2$, rồi $5$, nửa trái hết nên chép $7$, ra $(1, 2, 5, 7)$.

Tính đúng chứng minh bằng quy nạp theo độ dài đoạn. Đoạn dài không quá 1 đúng hiển nhiên. Đoạn dài hơn thì hai lời gọi con sắp đúng hai nửa, và bước gộp giữ bất biến “sau $k$ bước, $k$ phần tử đã ghi là $k$ phần tử nhỏ nhất của cả đoạn, theo thứ tự tăng”, vì phần tử nhỏ nhất chưa lấy luôn là đầu của một trong hai nửa.

Gộp tốn $O(r - l)$ nên $T(n) = 2T(n/2) + O(n) = O(n \log n)$, cỡ $3{,}5 \cdot 10^6$ phép toán với $n = 2 \cdot 10^5$. Mảng phụ khai báo một lần, toàn cục, dùng chung cho mọi lời gọi; nếu mỗi lời gọi tạo một vector mới thì tổng cấp phát lên $O(n \log n)$ và chậm đi thấy rõ. Lấy bên trái khi hai phần tử bằng nhau giữ nguyên thứ tự của các phần tử bằng nhau (sắp ổn định), và ở ví dụ dưới chính chỗ này quyết định cặp bằng nhau có bị tính hay không. Khi chỉ cần sắp xếp thì cứ gọi sort; ta học sắp xếp trộn vì bước gộp là nơi tính thêm những thứ khác ngay lúc ghép hai nửa.

Ví dụĐếm Cặp Ngược Thứ Tự

Đề. Cho dãy $N \le 2 \cdot 10^5$ số nguyên, $|a_i| \le 10^9$. Đếm số cặp $i < j$ với $a_i > a_j$ (nghịch thế; hai số bằng nhau không tính).

Lời giải. Duyệt mọi cặp tốn $2 \cdot 10^{10}$. Chia đôi tại $\mathrm{mid}$: mỗi nghịch thế có hai chỉ số cùng ở nửa trái, cùng ở nửa phải, hoặc chéo ($i < \mathrm{mid} \le j$). Hai loại đầu giao cho đệ quy. Số nghịch thế chéo chỉ phụ thuộc tập giá trị của mỗi nửa chứ không phụ thuộc thứ tự bên trong nửa, nên ta được quyền sắp mỗi nửa trước, và sắp xếp trộn làm sẵn việc đó. Trong bước gộp, mỗi lần lấy phần tử phải $a_j$ vì phần tử trái đang trỏ $a_i > a_j$ thì, do nửa trái tăng, mọi phần tử trái từ $i$ tới $\mathrm{mid} - 1$ đều lớn hơn $a_j$: cộng ngay $\mathrm{mid} - i$.

Mỗi cặp chéo $u > v$ được cộng đúng một lần, lúc $v$ được lấy: khi đó $u$ chưa được lấy, vì nếu $u$ được lấy trước thì phần tử đầu nửa phải lúc đó là $v' \le v$ và điều kiện lấy trái cho $u \le v' \le v$, mâu thuẫn. Bằng nhau thì lấy trái trước, nên cặp bằng nhau không bị cộng. Chạy tay trên $(3, 1, 2, 1)$: hai nửa có 1 nghịch thế mỗi bên và thành $(1, 3)$, $(1, 2)$; gộp thì $1$ với $1$ lấy trái, $3$ với $1$ lấy phải cộng 1, $3$ với $2$ lấy phải cộng 1. Tổng $1 + 1 + 2 = 4$. Đáp án tới $2 \cdot 10^{10}$ nên dùng ll.

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

const ll N = 2e5 + 5;
ll n, a[N], t[N];

ll calc(ll l, ll r) {
    if (r - l <= 1) return 0;
    ll mid = (l + r) >> 1;
    ll res = calc(l, mid) + calc(mid, r);
    ll i = l, j = mid, k = l;
    while (i < mid || j < r) {
        if (j == r || (i < mid && a[i] <= a[j])) t[k++] = a[i++];
        else {
            res += mid - i;
            t[k++] = a[j++];
        }
    }
    for (ll q = l; q < r; q++) a[q] = t[q];
    return res;
}

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

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    cout << calc(0, n) << '\n';
}

Input4
3 1 2 1

Output4

Đếm nghịch thế cũng làm được bằng cây Fenwick (bài 16); cách chia để trị này ngắn hơn và là điểm khởi đầu của CDQ (bài 60).

Phần cắt ngang: việc của bước gộp

Khuôn “trái, phải, chéo” của đếm nghịch thế dùng được cho nhiều bài về đoạn hay cặp. Bài thứ nhất: cho dãy số nguyên, có thể âm, tìm tổng lớn nhất của một đoạn con liên tiếp không rỗng. Bài này còn có lời giải tuyến tính khác; ta làm bằng chia để trị vì nó dạy đúng khuôn.

Chia dãy tại $\mathrm{mid}$. Mỗi đoạn $[i, j]$ nằm hẳn trong nửa trái, nằm hẳn trong nửa phải, hoặc cắt ngang đường chia ($i < \mathrm{mid} \le j$). Hai loại đầu giao cho đệ quy; bước gộp chỉ lo loại thứ ba. Đoạn cắt ngang là một hậu tố của nửa trái nối với một tiền tố của nửa phải, cả hai không rỗng. Hai phần chọn độc lập, nên ta chọn riêng hậu tố tốt nhất và tiền tố tốt nhất, mỗi thứ bằng một lượt quét từ $\mathrm{mid}$ ra một phía.

Có thể bỏ cả lượt quét bằng cách để mỗi lời gọi trả về bốn số mô tả đoạn của nó: tổng cả đoạn, tiền tố tốt nhất, hậu tố tốt nhất và đoạn con tốt nhất. Tiền tố tốt nhất của đoạn gộp nằm trong nửa trái, hoặc là cả nửa trái nối tiền tố tốt nhất của nửa phải; hậu tố đối xứng; đoạn tốt nhất là của nửa trái, của nửa phải, hoặc hậu tố trái nối tiền tố phải:

struct Info {
    ll sum, pre, suf, best;
};

Info combine(Info a, Info b) {
    return {a.sum + b.sum, max(a.pre, a.sum + b.pre), max(b.suf, b.sum + a.suf),
            max({a.best, b.best, a.suf + b.pre})};
}

Gộp tốn $O(1)$ nên $T(n) = 2T(n/2) + O(1) = O(n)$. Ý “tóm tắt mỗi đoạn bằng vài con số mà hai bản tóm tắt gộp được trong $O(1)$” chính là thứ mỗi nút của cây phân đoạn (bài 17) lưu.

Ví dụĐoạn Liên Tiếp Tốt Nhất

Đề. Cho dãy $N \le 2 \cdot 10^5$ số nguyên, $|a_i| \le 10^9$. In tổng lớn nhất của một đoạn con liên tiếp không rỗng.

Lời giải. Cài bản quét từ giữa ra. Với $a = (-4, 6, -2, 5, -7, 4, 3)$ và $\mathrm{mid} = 3$: nửa trái có đáp án riêng $6$, nửa phải có đáp án riêng $7$ (đoạn $4, 3$). Hậu tố của nửa trái có tổng $-2, 4, 0$, tốt nhất $4$; tiền tố của nửa phải có tổng $5, -2, 2, 5$, tốt nhất $5$. Đoạn cắt ngang tốt nhất $4 + 5 = 9$, đáp án $\max(6, 7, 9) = 9$. Hai biến hậu tố, tiền tố tốt nhất khởi tạo bằng $-10^{18}$ chứ không phải 0: khởi tạo 0 là cho phép phần rỗng, và với dãy toàn số âm chương trình sẽ in 0, tổng của một đoạn không tồn tại. Tổng tới $2 \cdot 10^{14}$ nên dùng ll; thời gian $O(n \log n)$.

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

const ll N = 2e5 + 5;
ll n, a[N];

ll solve(ll l, ll r) {
    if (r - l == 1) return a[l];
    ll mid = (l + r) >> 1;
    ll res = max(solve(l, mid), solve(mid, r));
    ll s = 0, bl = -1e18, br = -1e18;
    for (ll i = mid - 1; i >= l; i--) {
        s += a[i];
        bl = max(bl, s);
    }
    s = 0;
    for (ll j = mid; j < r; j++) {
        s += a[j];
        br = max(br, s);
    }
    return max(res, bl + br);
}

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

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> a[i];
    cout << solve(0, n) << '\n';
}

Input7
-4 6 -2 5 -7 4 3

Output9

Ví dụBình Phương Khoảng Cách Nhỏ Nhất

Đề. Cho $N \le 10^5$ điểm nguyên, $|x_i|, |y_i| \le 10^4$, hai điểm khác chỉ số có thể trùng tọa độ. In giá trị nhỏ nhất của $(x_i - x_j)^2 + (y_i - y_j)^2$ trên mọi cặp $i < j$: bài cặp điểm gần nhất (closest pair of points).

Lời giải. Sắp các điểm theo $x$ một lần, rồi chia theo chỉ số tại $\mathrm{mid}$; đường chia là $x = x_{\mathrm{mid}}$. Giải hai nửa bằng đệ quy, gọi $D$ là bình phương khoảng cách nhỏ hơn trong hai kết quả và $d = \sqrt D$. Còn lại các cặp chéo.

Cặp chéo muốn tốt hơn $D$ thì hai điểm cách nhau theo hoành độ chưa tới $d$, mà đường chia nằm giữa chúng, nên cả hai thuộc dải $|x - x_{\mathrm{mid}}| < d$. Sắp các điểm trong dải theo $y$; với điểm $p$, chỉ so với các điểm $q$ đứng trước có $p_y - q_y < d$. Những điểm đó cùng $p$ nằm trong hình chữ nhật $2d \times d$. Nửa trái của hình chữ nhật là hình vuông $d \times d$ mà các điểm bên trong đôi một cách nhau ít nhất $d$; chia nó thành bốn ô $\tfrac d2 \times \tfrac d2$, đường chéo mỗi ô là $d/\sqrt2 < d$ nên mỗi ô chứa không quá một điểm. Vậy hình chữ nhật chứa không quá 8 điểm kể cả $p$, và vòng so của mỗi điểm chạy tối đa 7 bước.

Mọi so sánh dùng bình phương bằng số nguyên, không có căn: điều kiện dải là $(x - x_{\mathrm{mid}})^2 < D$. Code gồm ba bước trong hàm solve(l, r), trả về đáp án của đoạn $[l, r)$ và để lại đoạn đó đã sắp theo $y$.

Bước 1: chia và giải hai nửa. Đoạn dưới hai điểm thì chưa có cặp nào, trả về vô cùng. Hoành độ đường chia mx phải lưu trước khi đệ quy, vì sau đó đoạn đã bị sắp lại theo $y$.

if (r - l <= 1) return 1e18;
ll mid = (l + r) >> 1, mx = p[mid].first;
ll d = min(solve(l, mid), solve(mid, r));

Bước 2: trộn hai nửa theo $y$. Hai nửa đã sắp theo $y$, trộn như sắp xếp trộn trong $O(r - l)$. Nhờ vậy không phải gọi sort theo $y$ ở mỗi lời gọi, việc sẽ nhân độ phức tạp thêm một thừa số $\log N$.

ll i = l, j = mid, k = l;
while (i < mid || j < r) {
    if (j == r || (i < mid && p[i].second <= p[j].second)) t[k++] = p[i++];
    else t[k++] = p[j++];
}
for (ll q = l; q < r; q++) p[q] = t[q];

Bước 3: quét dải. Đi qua đoạn theo thứ tự $y$, giữ các điểm của dải trong t[l..l + m). Điểm nằm ngoài dải thì bỏ. Điểm trong dải so với các điểm dải đứng trước, lùi dần khi hiệu tung độ còn nhỏ hơn $d$, rồi tự nhập vào dải. Theo lập luận ở trên, vòng lùi chạy tối đa 7 bước.

ll m = 0;
for (ll q = l; q < r; q++) {
    if (sq(p[q].first - mx) >= d) continue;
    for (ll s = m - 1; s >= 0 && sq(p[q].second - t[l + s].second) < d; s--)
        d = min(d, sq(p[q].first - t[l + s].first) + sq(p[q].second - t[l + s].second));
    t[l + m++] = p[q];
}

Điểm trùng nhau cho $D = 0$, khi đó dải rỗng và chương trình vẫn đúng. Với test ví dụ, nửa trái $\{(0,0), (1,1)\}$ cho $D = 2$ và không cặp chéo nào tốt hơn.

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

const ll N = 1e5 + 5;
ll n;
pair<ll, ll> p[N], t[N];

ll sq(ll v) {
    return v * v;
}

ll solve(ll l, ll r) {
    if (r - l <= 1) return 1e18;
    ll mid = (l + r) >> 1, mx = p[mid].first;
    ll d = min(solve(l, mid), solve(mid, r));
    ll i = l, j = mid, k = l;
    while (i < mid || j < r) {
        if (j == r || (i < mid && p[i].second <= p[j].second)) t[k++] = p[i++];
        else t[k++] = p[j++];
    }
    for (ll q = l; q < r; q++) p[q] = t[q];
    ll m = 0;
    for (ll q = l; q < r; q++) {
        if (sq(p[q].first - mx) >= d) continue;
        for (ll s = m - 1; s >= 0 && sq(p[q].second - t[l + s].second) < d; s--)
            d = min(d, sq(p[q].first - t[l + s].first) + sq(p[q].second - t[l + s].second));
        t[l + m++] = p[q];
    }
    return d;
}

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

    cin >> n;
    for (ll i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
    sort(p, p + n);
    cout << solve(0, n) << '\n';
}

Input5
0 0
3 4
1 1
9 9
1 4

Output2

$T(N) = 2T(N/2) + O(N)$, tức $O(N \log N)$ cộng một lần sắp ban đầu.

Chỉ đi vào một nhánh

Có khi bước gộp chẳng còn việc gì vì lời giải nằm trọn trong một bài con; ta chỉ cần biết nên đi vào bài con nào. Cây đệ quy khi đó rút thành một đường đi. Có hai dạng hay gặp.

Phần tử thứ $k$ (quickselect). Tìm số đứng thứ $k$ (đánh số từ 0) khi sắp tăng, không sắp cả dãy. Chọn một pivot $x$ ngẫu nhiên, chia các số thành ba nhóm: nhỏ hơn $x$ ($p$ số), bằng $x$ ($q$ số), lớn hơn $x$. Số cần tìm nằm trong nhóm nhỏ nếu $k < p$; bằng $x$ nếu $p \le k < p + q$; ngược lại nằm ở vị trí $k - p - q$ của nhóm lớn. Chỉ một nhóm cần đi tiếp.

mt19937 rng(712367);

ll kth(vector<ll> a, ll k) {
    while (true) {
        ll x = a[rng() % a.size()];
        vector<ll> lo, eq, hi;
        for (ll v : a) {
            if (v < x) lo.push_back(v);
            else if (v == x) eq.push_back(v);
            else hi.push_back(v);
        }
        if (k < (ll)lo.size()) a = lo;
        else if (k < (ll)(lo.size() + eq.size())) return x;
        else {
            k -= lo.size() + eq.size();
            a = hi;
        }
    }
}

Xấu nhất là $O(n^2)$ nếu pivot luôn rơi vào đầu mút, nhưng với pivot ngẫu nhiên trung bình chỉ $O(n)$. Gọi pivot là tốt nếu nó nằm trong nửa giữa của thứ tự sắp, xác suất ít nhất $1/2$; khi đó mỗi nhóm có không quá $3n/4$ phần tử. Trung bình chờ 2 vòng là gặp pivot tốt, mỗi vòng tốn tuyến tính theo cỡ hiện tại, nên trung bình tổng công việc không quá $2n\left(1 + \tfrac34 + \left(\tfrac34\right)^2 + \dots\right)$; tổng trong ngoặc bằng 4, nên cả bài trung bình không quá $8n$. Thư viện có nth_element làm đúng việc này tại chỗ.

Vị trí trong dãy sinh theo quy tắc. Nhiều đề cho một dãy sinh bằng quy tắc đệ quy, dài tới $10^{18}$, rồi hỏi phần tử thứ $p$. Không dựng được cả dãy, nhưng cấu trúc của nó đã là một lời gọi đệ quy sẵn. Ví dụ $S_0 = (0)$ và $S_k = S_{k-1}, k, S_{k-1}$: hai bản sao của $S_{k-1}$ kẹp số $k$ ở giữa. Vậy $S_2 = (0, 1, 0, 2, 0, 1, 0)$ và $|S_k| = 2^{k+1} - 1$. Phần tử thứ $p$ (từ 1) của $S_k$ chỉ ở ba chỗ: bản sao trái nếu $p \le |S_{k-1}|$; phần tử giữa, bằng $k$, nếu $p = |S_{k-1}| + 1$; còn lại là bản sao phải, nơi nó là phần tử thứ $p - |S_{k-1}| - 1$ của $S_{k-1}$. Ta chỉ lưu độ dài từng cấp rồi đi xuống một nhánh.

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

ll q, len[61];

ll at(ll k, ll p) {
    if (k == 0) return 0;
    if (p <= len[k - 1]) return at(k - 1, p);
    if (p == len[k - 1] + 1) return k;
    return at(k - 1, p - len[k - 1] - 1);
}

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

    len[0] = 1;
    for (ll k = 1; k <= 60; k++) len[k] = 2 * len[k - 1] + 1;
    cin >> q;
    while (q--) {
        ll k, p;
        cin >> k >> p;
        cout << at(k, p) << '\n';
    }
}

Input3
3 6
3 8
60 1000000000000000000

Output1
3
18

Mỗi truy vấn qua tối đa $k + 1 \le 61$ lời gọi. Nhìn kết quả thấy phần tử thứ $p$ của $S_k$ chính là số mũ của 2 trong $p$ (vì $10^{18} = 2^{18} \cdot 5^{18}$ nên ra 18), một công thức đóng; viết vài phần tử đầu ra giấy luôn đáng làm. Cùng khuôn này giải các bài về dãy bit tự đảo, xâu mở rộng hay thứ tự loại trong vòng tròn.

Ví dụĐếm Một Trong Dãy Gấp Đôi

Đề. Với $n \ge 0$, dãy $F(n)$ là $(n)$ nếu $n \le 1$, và là $F(\lfloor n/2 \rfloor)$, rồi $n \bmod 2$, rồi lại $F(\lfloor n/2 \rfloor)$ nếu $n > 1$. Cho $n \le 10^{18}$ và $l \le r$, đếm số phần tử bằng 1 ở các vị trí từ $l$ tới $r$ (đánh số từ 1).

Lời giải. Đếm trên đoạn bằng hiệu hai tiền tố: gọi $\mathrm{pre}(n, k)$ là số số 1 trong $k$ phần tử đầu của $F(n)$, đáp án là $\mathrm{pre}(n, r) - \mathrm{pre}(n, l - 1)$. Đặt $h = |F(\lfloor n/2 \rfloor)|$. Nếu $k \le h$, cả $k$ phần tử nằm trong bản sao trái: đi vào nó. Nếu $k > h$ thì $k$ phần tử đầu gồm trọn bản sao trái, phần tử giữa $n \bmod 2$, và $k - h - 1$ phần tử đầu của bản sao phải.

Đi vào bản sao phải là một nhánh, nhưng “trọn bản sao trái” lại là thêm một nhánh nữa, và hai nhánh mỗi mức là $O(n)$ lời gọi. Mẹo là $F(m)$ có đúng $m$ số 1: số số 1 thỏa $c(m) = 2c(\lfloor m/2 \rfloor) + m \bmod 2$, đúng hệ thức của chính $m = 2\lfloor m/2 \rfloor + m \bmod 2$, và hai bên bằng nhau ở $m \le 1$. Vậy trọn bản sao trái đóng góp $\lfloor n/2 \rfloor$ không cần gọi gì, và mỗi mức chỉ còn một lời gọi. Độ sâu là $\log_2 n \approx 60$ mức, mỗi mức tính $h$ thêm 60 bước.

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

ll n, l, r;

ll len(ll m) {
    return m <= 1 ? 1 : 2 * len(m / 2) + 1;
}

ll pre(ll m, ll k) {
    if (k <= 0) return 0;
    if (m <= 1) return m;
    ll h = len(m / 2);
    if (k <= h) return pre(m / 2, k);
    return m / 2 + m % 2 + pre(m / 2, k - h - 1);
}

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

    cin >> n >> l >> r;
    cout << pre(n, r) - pre(n, l - 1) << '\n';
}

Input5 2 6

Output3

Chia thành bốn phần: lát bảng bằng mảnh chữ L

Trên bảng vuông ta chia thành bốn phần tư. Ví dụ kinh điển: bảng $2^k \times 2^k$ khuyết đúng một ô; lát kín $4^k - 1$ ô còn lại bằng các mảnh chữ L, mỗi mảnh phủ 3 ô (chia hết vì $4^k$ chia 3 luôn dư 1). Chia thành bốn phần tư thì chỉ phần tư chứa ô khuyết là bài con cùng dạng, ba phần tư kia thì không. Mẹo là tạo ra ô khuyết: đặt một mảnh chữ L vào giữa bảng, phủ ba ô sát tâm thuộc ba phần tư không chứa ô khuyết. Giờ mỗi phần tư thiếu đúng một ô và là bài con cùng dạng; bảng $1 \times 1$ là điều kiện dừng. Tính đúng suy ra từ quy nạp theo $k$.

Chương trình dưới đọc cạnh $n$ (lũy thừa của 2) và ô khuyết $(h_r, h_c)$, tính từ 0, rồi in số hiệu mảnh phủ từng ô; ô khuyết giữ số 0. Hàm tile(r0, c0, s, hr, hc) lát hình vuông cạnh $s$, góc trên trái $(r_0, c_0)$, thiếu ô $(h_r, h_c)$. Hai mảng mr, mc là hai hàng và hai cột sát tâm.

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

ll n, hr, hc, id, b[130][130];

void tile(ll r0, ll c0, ll s, ll hr, ll hc) {
    if (s == 1) return;
    ll h = s / 2, cur = ++id;
    ll mr[2] = {r0 + h - 1, r0 + h}, mc[2] = {c0 + h - 1, c0 + h};
    for (ll i = 0; i < 2; i++)
        for (ll j = 0; j < 2; j++) {
            ll x = r0 + i * h, y = c0 + j * h;
            if (x <= hr && hr < x + h && y <= hc && hc < y + h) tile(x, y, h, hr, hc);
            else {
                b[mr[i]][mc[j]] = cur;
                tile(x, y, h, mr[i], mc[j]);
            }
        }
}

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

    cin >> n >> hr >> hc;
    tile(0, 0, n, hr, hc);
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) cout << b[i][j] << ' ';
        cout << '\n';
    }
}

Input4 1 2

Output2 2 3 3
2 1 0 3
4 1 1 5
4 4 5 5

Mảnh số 1 là mảnh giữa bảng, phủ các ô $(1, 1)$, $(2, 1)$, $(2, 2)$ của ba phần tư không chứa ô khuyết $(1, 2)$. Mỗi lời gọi tốn $O(1)$ ngoài đệ quy và sinh 4 bài con cạnh một nửa: $T(n) = 4T(n/2) + O(1)$ với $n$ là cạnh bảng. Ở đây $q = 4 > 1$ nên các lá quyết định, $O(n^{\log_2 4}) = O(n^2)$, đúng bằng số ô phải ghi.

Ví dụNhững Mảnh Giấy Hai Màu

Đề. Tờ giấy $N \times N$ ($N \le 128$, lũy thừa của 2), mỗi ô trắng (0) hoặc xanh (1). Một vùng vuông cùng màu thì giữ nguyên thành một mảnh; có cả hai màu thì chia thành bốn hình vuông bằng nhau và làm lại cho từng phần. In số mảnh trắng, rồi số mảnh xanh.

Lời giải. Đề đã là lời gọi chia bốn. Việc còn lại là hỏi nhanh “vùng này có cùng màu không”: đếm số ô xanh trong vùng bằng tổng tiền tố hai chiều (bài 02) trong $O(1)$; bằng 0 là mảnh trắng, bằng $k^2$ là mảnh xanh, còn lại thì chia bốn.

Bước 1: tổng tiền tố khi đọc. s[i][j] là số ô xanh trong hình chữ nhật từ $(1, 1)$ tới $(i, j)$, tính ngay khi đọc từng ô bằng công thức bao hàm loại trừ.

for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) {
        ll v;
        cin >> v;
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v;
    }

Bước 2: đếm ô xanh của một vùng. Vùng vuông cạnh $k$ có góc trên trái là ô $(x + 1, y + 1)$ (vì s đánh số từ 1) chứa get(x, y, k) ô xanh.

ll get(ll x, ll y, ll k) {
    return s[x + k][y + k] - s[x][y + k] - s[x + k][y] + s[x][y];
}

Bước 3: chia bốn. Vùng toàn trắng hay toàn xanh thì đếm một mảnh và dừng; ngược lại gọi đệ quy cho bốn hình vuông cạnh $k / 2$.

void go(ll x, ll y, ll k) {
    ll c = get(x, y, k);
    if (c == 0) {
        w++;
        return;
    }
    if (c == k * k) {
        g++;
        return;
    }
    ll h = k / 2;
    go(x, y, h);
    go(x, y + h, h);
    go(x + h, y, h);
    go(x + h, y + h, h);
}

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

ll n, w, g, s[130][130];

ll get(ll x, ll y, ll k) {
    return s[x + k][y + k] - s[x][y + k] - s[x + k][y] + s[x][y];
}

void go(ll x, ll y, ll k) {
    ll c = get(x, y, k);
    if (c == 0) {
        w++;
        return;
    }
    if (c == k * k) {
        g++;
        return;
    }
    ll h = k / 2;
    go(x, y, h);
    go(x, y + h, h);
    go(x + h, y, h);
    go(x + h, y + h, h);
}

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

    cin >> n;
    for (ll i = 1; i <= n; i++)
        for (ll j = 1; j <= n; j++) {
            ll v;
            cin >> v;
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + v;
        }
    go(0, 0, n);
    cout << w << '\n' << g << '\n';
}

Input4
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 1

Output4
3

Số vùng được xét không quá $1 + 4 + 16 + \dots < \tfrac43 N^2$, mỗi vùng $O(1)$, nên cả bài $O(N^2)$. Thiếu tổng tiền tố thì mỗi vùng tốn $k^2$ để kiểm, thành $O(N^2 \log N)$, vẫn qua với $N = 128$ nhưng không còn đẹp.