+7

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(logn),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)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,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ụ, 4210=1010102=25+23+2142_{10} = 101010_2 = 2^5 + 2^3 + 2^1. Dễ thấy, với một số nguyên không âm xx thì trong phân tích của nó thành tổng các lũy thừa cơ số 22 sẽ có tối đa log2(x)\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 mm 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ố 22 của mm. 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][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=23+22+20,m = 13 = 2^3 + 2^2 + 2^0, nên ta có thể tách nó ra thành thông tin của 33 đoạn nhỏ hơn: [2,14]=[2,9][10,13][14,14][2, 14] = [2, 9] \cup [10, 13] \cup [14, 14]. Tất nhiên, cũng chỉ có tối đa log2(x)\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ố 22. 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 QueriesRange 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,table, với table[i][j]table[i][j] dùng để lưu thông tin (kết quả) của đoạn con từ vị trí jj tới vị trí j+2i1,j + 2^i - 1, tức là lưu kết quả của đoạn con có độ dài 2i2^i bắt đầu từ vị trí jj trên mảng. Gọi maxnmaxn là kích thước tối đa của mảng cần kiểm soát thông tin, thì mảng tabletable sẽ phải kiểm soát được đoạn có độ dài lớn nhất bằng 2log2n2^{\left\lfloor{\log_2 n}\right\rfloor}. Do đó, kích thước của mảng tabletable ít nhất phải là (k+1)×maxn,(k + 1) \times maxn, với kk thỏa mãn klog2nk \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í 00 hay từ vị trí 11).

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 10710^7 phần tử trở lại, nên giá trị kk nên đặt ở khoảng 2525 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 ff là hàm lấy kết quả của một đoạn, ff 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à nn là độ dài mảng arrarr - mảng chúng ta đang cần kiểm soát. Vì một đoạn con [j,j+2i1][j, j + 2^i - 1] độ dài 2i2^i có thể tách ra làm hai đoạn độ dài 2i12^{i - 1}[j,j+2i11][j, j + 2^{i - 1} - 1][j+2i1,j+2i1],[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 tabletable:

table[i][j]={arr[j];neˆˊi=0,j+2i1n.f(table[i1][j],table[i1][j+2i1]);neˆˊi0,j+2i1n.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 ff sẽ thay đổi thành phép cộng hoặc hàm min\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×logn)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],[l, r], ta sẽ duyệt qua tất cả các lũy thừa cơ số 22 từ lớn nhất về nhỏ nhất. Nếu như một lũy thừa 2i2^i nhỏ hơn hoặc bằng độ dài đoạn con là rl+1,r - l + 1, thì ta sẽ ghi nhận kết quả của đoạn nhỏ [l,l+2i1],[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+2i,r][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(log(maxn))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 tabletable 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 min\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][1, 6] có thể tách thành hai đoạn [1,4][1, 4][3,6][3, 6] cũng không sao, giá trị nhỏ nhất của đoạn [1,6][1, 6] vẫn sẽ bằng giá trị nhỏ nhất giữa RMQ(1,4)RMQ(1, 4)RMQ(3,6)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][l, r] thành hai đoạn con là [l,l+2i1][l, l + 2^i - 1][r2i+1,r][r - 2^i + 1, r] với i=log2(rl+1)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][l, r] sẽ trở thành:

RMQ(l,r)=min(table[i][l],table[i][r2i+1])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ị log2\log_2 của rl+1,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 log2\log_2 của một số kiểu nguyên trong O(1)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)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)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ó nn người quen đến xếp hàng ủng hộ Tý, người thứ ii mang theo một số tiền là aia_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í ll tới vị trí r,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 nn - số lượng khách hàng.
  • Dòng thứ hai chứa nn số nguyên a1,a2,,ana_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 mm - số câu hỏi mà Tý tự đặt ra.
  • Trên mm dòng tiếp theo, dòng thứ ii chứa hai số nguyên dương li,ril_i, r_i thể hiện một câu hỏi mà Tý tự đặt ra.

Ràng buộc:

  • 1n1051 \le n \le 10^5.
  • 1ai109;i:1in1 \le a_i \le 10^9; \forall i: 1 \le i \le n.
  • 1m1061 \le m \le 10^6.
  • 1lirin;i:1im1 \le l_i \le r_i \le n; \forall i: 1 \le i \le m.

Subtasks:

  • Subtask 11 (30%30\% số điểm): 1n,m1001 \le n, m \le 100.
  • Subtask 22 (30%30\% số điểm): li=1,ri=n;i:1iml_i = 1, r_i = n; \forall i: 1 \le i \le m.
  • Subtask 33 (40%40\% số điểm): Không có ràng buộc gì thêm.

Output:

  • Trên mm 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][l, r] chính bằng ước chung lớn nhất của các số tiền aia_i trong đoạn đó. Như vậy bài toán quy về: Ứng với mỗi đoạn [l,r],[l, r], tính ước chung lớn nhất của các aia_ii[l,r]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][l, r] rồi tính ước chung lớn nhất với mỗi test case.

Độ phức tạp: O(n×m×logai)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(max(n×logai,m))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, GCD\text{GCD} có tính chất sau:

GCD(a,b,c)=GCD[GCD(a,b),c]=GCD[a,GCD(b,c)]\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 GCD\text{GCD} của một đoạn [l,r][l, r] thông qua các GCD\text{GCD} của các đoạn nhỏ của nó.

Mặt khác, nếu như ta tính GCD\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ụ, GCD(a,b,c)=GCD[GCD(a,b),GCD(b,c)]\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][l, r] thành hai đoạn là [l,l+2i1][l, l + 2^i - 1][r2i+1,r][r - 2^i + 1, r] rồi tính GCD\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 min\text{min} bằng hàm tính ước chung lớn nhất.

Độ phức tạp: O(n×logn×logai)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 nn số nguyên a1,a2,,ana_1, a_2, \dots, a_n. Dựa trên mảng số này, bạn cần phải trả lời mm truy vấn, mỗi câu hỏi gồm một cặp số kì diệu là ddtt.

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

al+dal+1,al+1+dal+2,,ar1+dar,art vaˋ ar+1>t (neˆˊu toˆˋn tại)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 nn.
  • Dòng thứ hai chứa nn số nguyên dương a1,a2,,ana_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 mm.
  • Trên mm dòng tiếp theo, mỗi dòng chứa một cặp số kì diệu ddtt - thể hiện một truy vấn.

Ràng buộc:

  • 1n,m1051 \le n, m \le 10^5.
  • 1ai106;i:1in1 \le a_i \le 10^6; \forall i: 1 \le i \le n.
  • a1t106a_1 \le t \le 10^6.
  • 0d1060 \le d \le 10^6.

Subtasks:

  • Subtask 11 (30%30\% số điểm): 1n,m1041 \le n, m \le 10^4.
  • Subtask 22 (70%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:

1
1
1
5
1
4

Ý 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ị rr thỏa mãn điều kiện đề bài (arta_r \le tar+1>ta_{r + 1} > t). Để tìm được vị trí rr này vô cùng đơn giản, bởi vì mảng AA đã đượ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í rr lớn nhất. Ngoài ra, bởi vì a1ta_1 \le t nên chắc chắn luôn luôn tồn tại giá trị rr.

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

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

Trước tiên, hãy bỏ qua điều kiện art<ar+1,a_r \le t < a_{r + 1},rr đã đượ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,l, ta chỉ cần quan tâm điều kiện:

al+dal+1,al+1+d<al+2,,ar1+dara_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ó:

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

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

bld,bl+1d,,br1db_l \le d, b_{l + 1} \le d, \dots, b_{r - 1} \le d

Tức là:

max(bl,bl+1,,br1)d ()\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 ll lùi dần từ rr về 1,1, liên tục cập nhật giá trị maxv=max(bl,bl+1,,br1)\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 ll nhỏ nhất tìm được.

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

Subtask 2

Gọi hàm G(x) (1xr)G(x) \ (1 \le x \le r) là một hàm kiểm tra vị trí xx có phải là vị trí sao cho đoạn [x,r][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 (xx thỏa mãn thì x+1x + 1 cũng thỏa mãn).

Như vậy, ta lại có thể tìm ra ll nhỏ nhất bằng cách tìm kiếm nhị phân kết hợp với hàm G(x)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)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:

max(bx,bx+1,,br1)d\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 max(bx,bx+1,,br1)\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),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 2i2^i trên mảng bb. Đâ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((n+m)×logn)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


©️ Tác giả: Vũ Quế Lâm từ Viblo


All rights reserved

Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí