10.5K 783 122

Đã đăng vào thg 6 28, 2023 8:44 SA 18 phút đọc

4.0K

Bảng thưa (Sparse Table)

I. Mở đầu

Những bài toán liên quan tới truy vấn trên đoạn là khá phổ biến trong lập trình thi đấu. Có thể kể đến một số bài toán tiêu biểu như: Tìm giá trị min/max trên đoạn (Range Minimum Queries), Tính tổng trên đoạn (Range Sum Queries),...Cùng với sự phát triển của các bài toán này, các cấu trúc dữ liệu để giải quyết chúng cũng được sinh ra như Cây phân đoạn (Interval Tree), Cây nhị phân chỉ số (Binary Indexed Tree) hay Cây quản lý phạm vi (Range Tree),...

Trong bài viết này, chúng ta sẽ cùng tìm hiểu về một cấu trúc dữ liệu rất mạnh để giải quyết bài toán Range Minimum Queries (RMQ), đó là Bảng thưa (Sparse Table). Đây là một cấu trúc dữ liệu có thể giải quyết rất nhiều loại truy vấn đoạn trong thời gian trung bình là $O(\log n),$ tuy nhiên nó phát huy sức mạnh thực sự trong bài toán RMQ khi có thể trả lời các truy vấn chỉ trong $O(1)$ . Cấu trúc dữ liệu này sẽ có ứng dụng lớn hơn nữa ở trong chuyên đề Đồ thị, khi được sử dụng ở bài toán Tìm cha chung gần nhất (LCA).

Nhược điểm duy nhất của cấu trúc dữ liệu này là nó không thể sử dụng khi dãy số bị thay đổi liên tục giữa các truy vấn. Khi đó, nếu sử dụng Sparse Table thì ta sẽ phải xây dựng lại toàn bộ cấu trúc dữ liệu. Trong trường hợp này, Binary Indexed Tree hoặc Interval Tree sẽ là cấu trúc dữ liệu tối ưu.

II. Ý tưởng chính

Ta biết rằng, mọi số nguyên không âm đều có thể phân tích thành tổng của các lũy thừa cơ số $2,$ và cách phân tích đó là duy nhất (bởi vì mỗi số nguyên không âm có duy nhất một biểu diễn trong hệ nhị phân). Lấy ví dụ, $42_{10} = 101010_2 = 2^5 + 2^3 + 2^1$ . Dễ thấy, với một số nguyên không âm $x$ thì trong phân tích của nó thành tổng các lũy thừa cơ số $2$ sẽ có tối đa $\left\lfloor{\log_2(x)}\right\rfloor$ số hạng.

Nhờ điều trên, một ý tưởng được phát triển để kiểm soát thông tin của các đoạn trên mảng. Thông tin của một đoạn gồm $m$ phần tử có thể được biểu diễn thông qua thông tin của các đoạn có độ dài nhỏ hơn, dựa trên biểu diễn tổng lũy thừa cơ số $2$ của $m$ . Các đoạn nhỏ hơn sẽ có độ dài đúng bằng các số hạng trong biểu diễn đó. Lấy ví dụ, ta cần lưu thông tin của một đoạn thuộc vị trí $[2, 14]$ trên một mảng chẳng hạn, thì bởi vì độ dài đoạn này là $m = 13 = 2^3 + 2^2 + 2^0,$ nên ta có thể tách nó ra thành thông tin của $3$ đoạn nhỏ hơn: $[2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]$ . Tất nhiên, cũng chỉ có tối đa $\left\lfloor{\log_2(x)}\right\rfloor$ đoạn con.

Đây chính là ý tưởng chính của cấu trúc dữ liệu Sparse Table. Khi sử dụng Sparse Table trong các bài toán liên quan tới truy vấn trên nhiều đoạn, ta sẽ tính toán trước kết quả của mọi đoạn con với độ dài là một lũy thừa cơ số $2$ . Sau đó, với mỗi truy vấn cần tính toán, ta sẽ tách đoạn con trong truy vấn đó thành các đoạn nhỏ hơn (dựa trên biểu diễn nhị phân của độ dài), rồi tìm kết quả tương ứng trên bảng đã tính toán trước, cuối cùng kết hợp các đáp án của các đoạn nhỏ lại với nhau thành đáp án cuối cùng.

Sau đây, ta sẽ cùng xem xét các bước triển khai của cấu trúc dữ liệu này, thông qua hai ứng dụng chính của nó là Range Minimum Queries và Range Sum Queries.

III. Các bước triển khai

1. Tiền xử lý

Ta sử dụng một mảng hai chiều $table,$ với $table[i][j]$ dùng để lưu thông tin (kết quả) của đoạn con từ vị trí $j$ tới vị trí $j + 2^i - 1,$ tức là lưu kết quả của đoạn con có độ dài $2^i$ bắt đầu từ vị trí $j$ trên mảng. Gọi $maxn$ là kích thước tối đa của mảng cần kiểm soát thông tin, thì mảng $table$ sẽ phải kiểm soát được đoạn có độ dài lớn nhất bằng $2^{\left\lfloor{\log_2 n}\right\rfloor}$ . Do đó, kích thước của mảng $table$ ít nhất phải là $(k + 1) \times maxn,$ với $k$ thỏa mãn $k \ge \left\lfloor{\log_2 n}\right\rfloor$ . Ngoài ra các bạn cũng cần điều chỉnh kích thước cho phù hợp với cách đánh số mảng của mình (từ vị trí $0$ hay từ vị trí $1$ ).

Với các bài toán lập trình thi đấu, kích thước của mảng một chiều thường rơi vào khoảng $10^7$ phần tử trở lại, nên giá trị $k$ nên đặt ở khoảng $25$ là hợp lý. Các bạn nên khai báo một mảng tĩnh hai chiều để tối ưu về thời gian.

long long st[k + 1][maxn + 1]; 
// int st[k + 1][maxn] nếu đánh số mảng từ vị trí 0.

Gọi $f$ là hàm lấy kết quả của một đoạn, $f$ sẽ lấy tổng hoặc giá trị nhỏ nhất tùy thuộc vào bài toán là RMQ hay RSQ và $n$ là độ dài mảng $arr$ - mảng chúng ta đang cần kiểm soát. Vì một đoạn con $[j, j + 2^i - 1]$ độ dài $2^i$ có thể tách ra làm hai đoạn độ dài $2^{i - 1}$ là $[j, j + 2^{i - 1} - 1]$ và $[j + 2^{i - 1}, j + 2^i - 1],$ nên ta có công thức truy hồi để xây dựng bảng $table$ :

$table[i][j] = \begin{cases} arr[j]; &\text{nếu } i = 0, j + 2^i - 1 \le n. \\ f\Big(table[i - 1][j], table\big[i - 1\big]\big[j + 2^{i - 1}\big]\Big); &\text{nếu } i \ne 0, j + 2^i - 1 \le n. \end{cases}$

long long arr[maxn + 1];

// Khởi tạo mảng table kích thước (k + 1) * n cho mảng arr.
void pre_compute(int n, int k)
{
    for (int j = 1; j <= n; ++j)
        table[0][j] = arr[j];
		
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}

Hàm $f$ sẽ thay đổi thành phép cộng hoặc hàm $\text{min}$ tùy vào bài toán yêu cầu. Bước khởi tạo này có độ phức tạp là $O(n \times \log n)$ .

2. Áp dụng vào bài toán Range Sum Queries

Trong bài toán này, ta mong muốn tìm tổng của các đoạn con. Vì vậy, bước khởi tạo sẽ trở thành:

long long arr[maxn + 1];
long long table[k + 1][maxn + 1];

void pre_compute(int n, int k)
{
    for (int j = 1; j <= n; ++j)
        table[0][j] = arr[j];
		
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            table[i][j] = table[i - 1][j] + table[i - 1][j + (1 << (i - 1))];
}

Kế đến, để tính tổng của một đoạn con $[l, r],$ ta sẽ duyệt qua tất cả các lũy thừa cơ số $2$ từ lớn nhất về nhỏ nhất. Nếu như một lũy thừa $2^i$ nhỏ hơn hoặc bằng độ dài đoạn con là $r - l + 1,$ thì ta sẽ ghi nhận kết quả của đoạn nhỏ $[l, l + 2^i - 1],$ rồi tiếp tục tính toán với đoạn còn lại là $[l + 2^i, r]$ :

long long query(int l, int r)
{
    long long ans = 0;
    for (int i = k; i >= 0; --i)
        if ((1 << i) <= (r - l + 1))
        {
            ans += table[i][l];
            l += (1 << i);
        }
		
    return ans;
}

Độ phức tạp của một thao tác query là $O(k) = O\big(\log (maxn)\big)$ .

3. Áp dụng vào bài toán Range Minimum Queries

Đây là loại bài toán mà sức mạnh thật sự của Sparse Table được phát huy. Trước tiên, ta vẫn khởi tạo bảng $table$ giống như bài toán Range Sum Queries, nhưng thay thế phép toán cộng bằng phép toán lấy $\text{min}$ .

long long arr[maxn + 1];
long long table[k + 1][maxn + 1];

void pre_compute(int n, int k)
{
    for (int j = 1; j <= n; ++j)
        table[0][j] = arr[j];
		
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            table[i][j] = min(table[i - 1][j] + table[i - 1][j + (1 << (i - 1))]);
}

Ta biết rằng, với truy vấn lấy giá trị nhỏ nhất thì việc một phần tử được xét ở một hoặc hai hay nhiều đoạn nhỏ cũng không quan trọng, chẳng hạn như đoạn $[1, 6]$ có thể tách thành hai đoạn $[1, 4]$ và $[3, 6]$ cũng không sao, giá trị nhỏ nhất của đoạn $[1, 6]$ vẫn sẽ bằng giá trị nhỏ nhất giữa $RMQ(1, 4)$ và $RMQ(3, 6)$ gộp lại.

Do đó, thay vì phải chia đoạn lớn ra thành nhiều đoạn nhỏ, thì ta chỉ cần chia đoạn $[l, r]$ thành hai đoạn con là $[l, l + 2^i - 1]$ và $[r - 2^i + 1, r]$ với $i = \left\lfloor{\log_2(r - l + 1)}\right\rfloor$ . Khi đó, công thức để tính kết quả cho đoạn $[l, r]$ sẽ trở thành:

$RMQ(l, r) = \text{min}\Big(table[i][l], table\big[i\big]\big[r - 2^i + 1\big]\Big)$

Để tính nhanh giá trị $\log_2$ của $r - l + 1,$ ta có thể áp dụng ngay hàm log2() trong thư viện <cmath> của C++ như sau:

int log2_floor(unsigned long long n)
{
    return floor(log2(n * 1.0));
}

Tuy nhiên, hàm này nhận vào đối số là một số kiểu thực, cho nên nếu như truyền số nguyên vào, sẽ tốn thêm thời gian ép kiểu, dẫn đến trường hợp có thể TLE nếu như phải trả lời quá nhiều truy vấn. Trong trường hợp đó, các bạn có thể áp dụng đoạn code dưới đây để tính nhanh ra $\log_2$ của một số kiểu nguyên trong $O(1)$ :

Code C++20:

// Nếu sử dụng C++20.
#include <bit>

using namespace std;

int log2_floor(unsigned long long n) 
{
    return bit_width(n) - 1;
}

Các phiên bản trước C++20:

int log2_floor(unsigned long long n) 
{
    // Số bit 0 đứng đầu của 1 trừ đi số bit 0 đứng đầu của n.
    return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1;
}

Cuối cùng, với mỗi truy vấn ta chỉ cần trả về kết quả trong $O(1)$ :

long long query(int l, int r)
{
    int i = log2_floor(r - l + 1); // int i = (int) log2((double) r - l + 1);
    return min(table[i][l], table[i][r - (1 << i) + 1]);
}

4. Mở rộng

Qua hai ví dụ, ta đã có thể mường tượng được ứng dụng của Sparse Table, đó là dùng để giải quyết các bài toán truy vấn trên đoạn mà có thể tính toán được thông qua các đoạn con nhỏ hơn nó. Tuy nhiên, tùy vào bài toán mà chúng ta sẽ lựa chọn nên tách một đoạn con thành nhiều đoạn nhỏ để gộp kết quả hay chỉ cần tách một lần giống như ở bài toán RMQ.

Thực tế cho thấy, phương pháp tách đoạn đúng một lần để lấy kết quả giống như thao tác ở bài toán RMQ chỉ có thể áp dụng với các dạng truy vấn mà không thay đổi kết quả nếu như ta xử lý một phần tử trùng lặp nhiều lần. RMQ là một ví dụ kinh điển, ngoài ra truy vấn ước chung lớn nhất hay bội chung nhỏ nhất cũng có thể xử lý theo cách tương tự.

Có một số cấu trúc dữ liệu khác có thể hỗ trợ xử lý nhiều loại truy vấn kết hợp mà vẫn trả về kết quả trong $O(1)$ . Tiêu biểu trong số đó có thể kể đến Disjoint Sparse Table hay Sqrt Tree. Chúng ta sẽ đề cập đến các cấu trúc dữ liệu này ở những chuyên đề khác.

IV. Bài tập áp dụng

1. Mua Bánh

Đề bài

Tý mới mở một tiệm bánh ngọt siêu to khổng lồ. Ngày đầu tiên khai trương, có $n$ người quen đến xếp hàng ủng hộ Tý, người thứ $i$ mang theo một số tiền là $a_i$ đồng. Cầm trên tay bản danh sách khách hàng, Tý chợt nảy ra một câu hỏi trong đầu: Nếu như chỉ bán bánh cho các vị khách từ vị trí $l$ tới vị trí $r,$ thì nên để giá bánh là bao nhiêu để thu được lợi nhuận lớn nhất?

Do mới mở hàng nên Tý chưa có kinh nghiệm ra giá, cậu không biết nên bán bánh với giá bao nhiêu tiền. Biết rằng, mỗi vị khách đến cửa hàng đều mong muốn mua bánh hết số tiền họ mang theo, và Tý cũng muốn thu được tiền nhiều nhất có thể. Vì vậy, cậu cần tìm một giá tiền lớn nhất để bán bánh, từ đó thu được lợi nhuận lớn nhất.

Yêu cầu: Giúp Tý chọn giá tiền lớn nhất có thể cho những chiếc bánh sao cho khi bán hàng, các khách mua đều không bị thừa hay thiếu tiền?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ - số lượng khách hàng.
Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách - lượng tiền mà mỗi khách hàng mang theo.
Dòng thứ ba chứa số nguyên dương $m$ - số câu hỏi mà Tý tự đặt ra.
Trên $m$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên dương $l_i, r_i$ thể hiện một câu hỏi mà Tý tự đặt ra.

Ràng buộc:

$1 \le n \le 10^5$ .
$1 \le a_i \le 10^9; \forall i: 1 \le i \le n$ .
$1 \le m \le 10^6$ .
$1 \le l_i \le r_i \le n; \forall i: 1 \le i \le m$ .

Subtasks:

Subtask $1$ ( $30\%$ số điểm): $1 \le n, m \le 100$ .
Subtask $2$ ( $30\%$ số điểm): $l_i = 1, r_i = n; \forall i: 1 \le i \le m$ .
Subtask $3$ ( $40\%$ số điểm): Không có ràng buộc gì thêm.

Output:

Trên $m$ dòng, mỗi dòng đưa ra giá bánh mà Tý sẽ lựa chọn cho trường hợp tương ứng.

Sample Input:

8
7 2 3 5 10 3 12 18
3
1 3
6 8
4 5

Sample Output:

1
3
5

Ý tưởng

Có thể nhận thấy rằng, giá bánh lớn nhất có thể chọn cho tập khách hàng thuộc đoạn $[l, r]$ chính bằng ước chung lớn nhất của các số tiền $a_i$ trong đoạn đó. Như vậy bài toán quy về: Ứng với mỗi đoạn $[l, r],$ tính ước chung lớn nhất của các $a_i$ mà $i \in [l, r]$ .

Subtask 1

Subtask này ta dễ dàng giải quyết bằng cách duyệt lại từng vị trí trong đoạn $[l, r]$ rồi tính ước chung lớn nhất với mỗi test case.

Độ phức tạp: $O(n \times m \times \log a_i)$ .

Subtask 2

Dễ thấy, với mọi test case kết quả đều là ước chung lớn nhất của cả dãy số. Vì vậy ta tính trước ước chung lớn nhất của dãy số rồi in ra ở mỗi test case.

Độ phức tạp: $O\big(\text{max}(n \times \log a_i, m)\big)$ .

Subtask 3

Subtask này, ta sẽ áp dụng Sparse Table để giải tối ưu.

Ta biết rằng, $\text{GCD}$ có tính chất sau:

$\text{GCD}(a, b, c) = \text{GCD}\big[\text{GCD}(a, b), c\big] = \text{GCD}\big[a, \text{GCD}(b, c)\big]$

Như vậy, ta có thể tính $\text{GCD}$ của một đoạn $[l, r]$ thông qua các $\text{GCD}$ của các đoạn nhỏ của nó.

Mặt khác, nếu như ta tính $\text{GCD}$ của một đoạn nhỏ trùng nhiều lần rồi mới gộp vào đoạn lớn, thì kết quả cũng vẫn không thay đổi. Ví dụ, $\text{GCD}(a, b, c) = \text{GCD}\big[\text{GCD}(a, b), \text{GCD}(b, c)\big]$ . Tính chất này giống với bài toán RMQ, do đó ta chỉ cần tách đoạn $[l, r]$ thành hai đoạn là $[l, l + 2^i - 1]$ và $[r - 2^i + 1, r]$ rồi tính $\text{GCD}$ của hai đoạn này là xong.

Ta sẽ triển khai tương tự với bài toán RMQ, chỉ cần thay thế phép toán lấy $\text{min}$ bằng hàm tính ước chung lớn nhất.

Độ phức tạp: $O(n \times \log n \times \log a_i)$ .

Cài đặt

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#define int long long

using namespace std;

// Tính log2 của một số n bất kì trong O(1).
int log2_floor(int n)
{
    return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1;
}

// Khởi tạo Sparse Table.
vector < vector < int > > pre_compute(int n, vector < int > &a)
{
    int k = log2_floor(n);
    vector < vector < int > > table(k + 1, vector < int >(n + 1));

    for (int j = 1; j <= n; ++j)
        table[0][j] = a[j];

    for (int i = 1; i <= k; ++i)
        for (int j = 1; j + (1 << i) - 1 <= n; ++j)
            table[i][j] = __gcd(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);

    return table;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Nhập dữ liệu n và mảng a.
    int n;
    cin >> n;

    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    // Khởi tạo Sparse Table lưu GCD của các đoạn con độ dài là lũy thừa của 2.
    vector < vector < int > > table = pre_compute(n, a);

    // Xử lý các truy vấn.
    int m;
    cin >> m;

    while (m--)
    {
        int l, r;
        cin >> l >> r;

        // Đặt i = log2(r - l + 1).
        int i = log2_floor(r - l + 1);

        // GCD(l, r) = GCD của 2^i phần tử đầu và 2^i phần tử cuối của đoạn [l, r] gộp lại.
        cout << __gcd(table[i][l], table[i][r - (1 << i) + 1]) << endl;
    }

    return 0;
}

2. Cặp Số Kì Diệu

Đề bài

Cho trước một mảng gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ . Dựa trên mảng số này, bạn cần phải trả lời $m$ truy vấn, mỗi câu hỏi gồm một cặp số kì diệu là $d$ và $t$ .

Nhiệm vụ của bạn ở mỗi truy vấn là cần tìm ra vị trí $l$ nhỏ nhất sao cho với vị trí $l$ đó, thì tồn tại một vị trí $r \ (r \ge l)$ thỏa mãn:

$a_l + d \ge a_{l + 1}, a_{l + 1} + d \ge a_{l + 2}, \dots, a_{r - 1} + d \ge a_r, a_r \le t \text{ và } a_{r + 1} > t \ (\text{nếu tồn tại})$

Yêu cầu: Hãy trả lời tất cả các truy vấn?

Input:

Dòng đầu tiên chứa số nguyên dương $n$ .
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \dots, a_n$ phân tách nhau bởi dấu cách.
Dòng thứ ba chứa chứa số nguyên dương $m$ .
Trên $m$ dòng tiếp theo, mỗi dòng chứa một cặp số kì diệu $d$ và $t$ - thể hiện một truy vấn.

Ràng buộc:

$1 \le n, m \le 10^5$ .
$1 \le a_i \le 10^6; \forall i: 1 \le i \le n$ .
$a_1 \le t \le 10^6$ .
$0 \le d \le 10^6$ .

Subtasks:

Subtask $1$ ( $30\%$ số điểm): $1 \le n, m \le 10^4$ .
Subtask $2$ ( $70\%$ số điểm): Không có ràng buộc gì thêm.

Output:

Với mỗi truy vấn, in ra kết quả trên một dòng.

Sample Input:

5
1 2 3 10 50
6
1 1
5 3
11 7
100000 1
1000000 1000000
11 6

Sample Output:

Ý tưởng

Subtask 1

Nhận xét rằng, với mỗi truy vấn, chắc chắn chỉ tồn tại duy nhất một giá trị $r$ thỏa mãn điều kiện đề bài ( $a_r \le t$ và $a_{r + 1} > t$ ). Để tìm được vị trí $r$ này vô cùng đơn giản, bởi vì mảng $A$ đã được sắp xếp tăng dần, nên ta hoàn toàn có thể dùng tìm kiếm nhị phân để tìm ra vị trí $r$ lớn nhất. Ngoài ra, bởi vì $a_1 \le t$ nên chắc chắn luôn luôn tồn tại giá trị $r$ .

Tuy nhiên, đề bài yêu cầu ta đi tìm vị trí $l$ chứ không phải vị trí $r$ .

Ta nhận thấy rằng, bởi vì ở mỗi truy vấn, $r$ là duy nhất nên ta có thể đi tìm $l$ nhỏ nhất dựa vào $r$ .

Trước tiên, hãy bỏ qua điều kiện $a_r \le t < a_{r + 1},$ vì $r$ đã được tìm cố định trước ở mỗi truy vấn, nên điều kiện này mặc nhiên luôn luôn thỏa mãn. Lúc này, với một vị trí $l,$ ta chỉ cần quan tâm điều kiện:

$a_l + d \le a_{l + 1}, a_{l + 1} + d < a_{l + 2}, \dots, a_{r - 1} + d \le a_r$

Biến đổi một chút ta sẽ có:

$a_{l + 1} - a_l \le d, a_{l + 2} - a_{l + 1} \le d, \dots, a_r - a_{r - 1} \le d \ (*)$

Đặt $b_i = a_{i + 1} - a_i \ (1 \le i < n)$ thì điều kiện $(*)$ trở thành:

$b_l \le d, b_{l + 1} \le d, \dots, b_{r - 1} \le d$

Tức là:

$\text{max}(b_l, b_{l + 1}, \dots, b_{r - 1}) \le d \ (**)$

Ở subtask này, ta chỉ cần sử dụng một vòng lặp duyệt $l$ lùi dần từ $r$ về $1,$ liên tục cập nhật giá trị $\text{maxv} = \text{max}(b_l, b_{l + 1}, \dots, b_{r - 1})$ và kiểm tra tới khi điều kiện $(**)$ không còn thỏa mãn nữa thì in ra $l$ nhỏ nhất tìm được.

Độ phức tạp: $O\big(m \times (\log n + n)\big)$ .

Subtask 2

Gọi hàm $G(x) \ (1 \le x \le r)$ là một hàm kiểm tra vị trí $x$ có phải là vị trí sao cho đoạn $[x, r]$ thỏa mãn điều kiện đề bài hay không, thì ta nhận thấy hàm này sẽ là một hàm thỏa mãn định lý chính của tìm kiếm nhị phân ( $x$ thỏa mãn thì $x + 1$ cũng thỏa mãn).

Như vậy, ta lại có thể tìm ra $l$ nhỏ nhất bằng cách tìm kiếm nhị phân kết hợp với hàm $G(x)$ để kiểm tra một vị trí đang thử chọn có thỏa mãn hay không. Và điều kiện để hàm $G(x)$ sẽ trả về đúng chính là khi điều kiện $(**)$ thỏa mãn, ngược lại trả về sai:

$\text{max}(b_x, b_{x + 1}, \dots, b_{r - 1}) \le d$

Tuy nhiên, ta cần cải tiến việc tìm ra $\text{max}(b_x, b_{x + 1}, \dots, b_{r - 1})$ . Điều này có thể thực hiện nhanh trong $O(1),$ nếu như ta khởi tạo trước một Sparse Table lưu trữ toàn bộ các giá trị max các đoạn có độ dài $2^i$ trên mảng $b$ . Đây là bài toán RMQ cơ bản, các bạn có thể tham khảo lại kiến thức ở phần lý thuyết bên trên.

Độ phức tạp: $O\big((n + m) \times \log n\big)$ .

Cài đặt

#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#define int long long

using namespace std;

// Tính log2 của một số n bất kì trong O(1).
int log2_floor(int n)
{
    return n ? __builtin_clzll(1) - __builtin_clzll(n) : -1;
}

// Khởi tạo Sparse Table tính max của các đoạn trên mảng b[i] = a[i + 1] - a[i].
vector < vector < int > > pre_compute(int n, vector < int > &a)
{
    int k = log2_floor(n - 1);
    vector < vector < int > > table(k + 1, vector < int >(n));

    for (int j = 1; j < n; ++j)
        table[0][j] = a[j + 1] - a[j];

    for (int i = 1; i <= k; ++i)
        for (int j = 1; j + (1 << i) - 1 < n; ++j)
            table[i][j] = max(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);

    return table;
}

// Kiểm tra một vị trí x có phải là một kết quả hợp lệ không.
bool check(int x, int r, int d, vector < vector < int > > &table)
{
    // Tìm giá trị lớn nhất của đoạn b[x...(r - 1)].
    int i = log2_floor(r - x + 1);
    int max_range = max(table[i][x], table[i][r - (1 << i) + 1]);

    // Vị trí x hợp lệ nếu như max đoạn b[x...(r - 1)] <= d.
    return max_range <= d;
}

// Trả lời một truy vấn.
void query(int t, int d, vector < int > &a, vector < vector < int > > &table)
{
    // Trước tiên tìm kiếm nhị phân r lớn nhất sao cho a[r] <= t.
    int r = upper_bound(a.begin() + 1, a.end(), t) - a.begin() - 1;
    int l = r;

    // Tiếp tục tìm kiếm nhị phân l (1 <= l <= r) thỏa mãn yêu cầu đề bài.
    int low = 1, high = r - 1;
    while (low <= high)
    {
        int mid = (low + high) >> 1;

        if (check(mid, r - 1, d, table))
            l = mid, high = mid - 1;
        else
            low = mid + 1;
    }

    cout << l << endl;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    // Nhập dữ liệu n và mảng a.
    int n;
    cin >> n;

    vector < int > a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    vector < vector < int > > table = pre_compute(n, a);

    int m;
    cin >> m;

    while (m--)
    {
        int d, t;
        cin >> d >> t;

        query(d, t, a, table);
    }

    return 0;
}

V. Tài liệu tham khảo

I. Mở đầu

II. Ý tưởng chính

III. Các bước triển khai

1. Tiền xử lý

2. Áp dụng vào bài toán Range Sum Queries

3. Áp dụng vào bài toán Range Minimum Queries

4. Mở rộng

IV. Bài tập áp dụng

1. Mua Bánh

Đề bài

Ý tưởng

Subtask 1

Subtask 2

Subtask 3

Cài đặt

2. Cặp Số Kì Diệu

Đề bài

Ý tưởng

Subtask 1

Subtask 2

Cài đặt

V. Tài liệu tham khảo

Mục lục