Hiểu bài toán

Bài toán yêu cầu xử lý một dãy số gồm n số nguyên dương đại diện cho chiều cao của n chàng trai. Sau đó, có k truy vấn, mỗi truy vấn cho trước một số m (m ≤ n), yêu cầu tìm giá trị lớn nhất trong m phần tử đầu tiên của dãy (từ vị trí 1 đến m). Nhóm các giải pháp được cung cấp đều sử dụng cùng một chiến lược tối ưu: tiền xử lý để trả lời truy vấn trong thời gian常数.

Các cách tiếp cận

Cách Tiền xử lý mảng tiền tố (Prefix Maximum)

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

void solve(){
    int n, k;
    cin >> n >> k;

    vector<long long> a(n+1), pref(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = max(pref[i-1], a[i]);
    }

    while (k--) {
        int m;
        cin >> m;
        cout << pref[m] << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Đây là phương pháp hiệu quả nhất và được sử dụng trong các giải pháp mẫu. Ý tưởng là xây dựng một mảng phụ (pref), trong đó pref[i] lưu giá trị lớn nhất của dãy từ phần tử 1 đến i. Cụ thể:

1. Khởi tạo mảng pref với kích thước n+1, pref[0] = 0.
2. Duyệt từ i = 1 đến n, cập nhật pref[i] = max(pref[i-1], a[i]).
3. Với mỗi truy vấn m, ta chỉ cần in ra giá trị pref[m] ngay lập tức. Cách này giúp giảm thời gian xử lý truy vấn từ O(n) (nếu duyệt lại mỗi lần) xuống O(1).

Cách Một mảng duy nhất (Single Array Prefix)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,a[1000011],b[1000011],m;
int main() {
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]= max(b[i-1],a[i]);
    }
    while(k--){
        cin>>m;
        cout<<b[m]<<endl;
    }
    }

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Giải pháp này giống về logic với cách 1, chỉ khác biệt về mặt triển khai:

1. Sử dụng mảng b để lưu trữ kết quả tiền tố thay vì tạo riêng một mảng pref.
2. Quá trình xây dựng mảng b được thực hiện ngay trong vòng lặp đọc dữ liệu đầu vào.
3. Mảng a ban đầu vẫn được lưu trữ nhưng không dùng đến sau bước tính toán, có thể tối ưu bằng cách không khai báo mảng a mà chỉ dùng một biến tạm nếu muốn tiết kiệm bộ nhớ. Độ phức tạp về thời gian và bộ nhớ tương đương cách 1.

Cách Biến lưu trữ động (Dynamic Variable)

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

long long n,x,a[1000011],b[1000011],k;
int main() {
    cin >> n >> k ;
    for(long long  i = 1; i <= n; i++) {
            cin >> a[i];
    }
    long long s=0;
    for(long long i=1;i<=n;i++){
    s=max(s,a[i]);
    b[i]=s;
    }
    while(k--){
            long long x,s=0;
    cin >> x;
    cout << b[x] << endl;
    }
                    return 0;
}

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Giải pháp này tách biệt rõ ràng các giai đoạn:

1. Đọc toàn bộ dữ liệu vào mảng a.
2. Duyệt một vòng lặp riêng để tính mảng b (tiền tố max) bằng cách sử dụng biến trung gian s.
3. Xử lý truy vấn. Về bản chất, đây là cách viết chi tiết hơn của phương pháp prefix max. Việc tách vòng lặp nhập và vòng lặp tính max giúp code dễ đọc hơn nhưng không cải thiện độ phức tạp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể được chia thành 2 giai đoạn độc lập: Giai đoạn tiền xử lý (O(n)) để chuẩn bị dữ liệu, và giai đoạn trả lời truy vấn (O(1) mỗi truy vấn).
• Khái niệm 'Mảng tiền tố' (Prefix Array) là chìa khóa: Nếu chỉ cần biết max của đoạn [1, i], ta có thể tính nó dựa trên max của đoạn [1, i-1] và giá trị tại i.

Lỗi thường gặp

• Lỗi truy cập ngoài biên mảng: Cần chú ý khai báo mảng có kích thước tối thiểu là n+1 và xử lý chỉ số từ 1 đến n hoặc 0 đến n-1 một cách nhất quán.
• Kiểu dữ liệu: Chiều cao có thể lên tới 10^9, nên cần sử dụng kiểu dữ liệu 64-bit (long long) để đảm bảo an toàn khi so sánh và lưu trữ.