Hiểu bài toán

Bài toán yêu cầu xử lý các truy vấn cập nhật và một truy vấn hỏi. Ban đầu có một dãy số, nhưng thay vì lưu trữ rõ ràng, chúng ta nhận q truy vấn. Mỗi truy vấn dạng (a, b) có nghĩa là tăng giá trị tại chỉ số a lên b (tức là A[a] += b). Sau khi xử lý xong q truy vấn này, chúng ta nhận một số nguyên k và cần tìm chỉ số a đầu tiên sao cho tổng số lượng phần tử từ a trở xuống (tức là tổng các giá trị A[i] với i <= a) lớn hơn hoặc bằng k. Nói cách khác, nếu coi dãy số A là kết quả cuối cùng sau các cập nhật, ta cần tìm chỉ số a sao cho tổng tiền tố (prefix sum) tại a >= k.

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

Cách Sử dụng Map (Tự động sắp xếp)

// LuyenCode/THPTTD_20.cpp
#include <bits/stdc++.h>

#define ll long long

using namespace std;

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
     freopen("AQUERY.inp", "r", stdin);
     freopen("AQUERY.out", "w", stdout);
    int q;
    ll k;
    cin >> q;
    ll a, b;
    map<ll, ll> m;
    for (int i = 0; i < q; i++)
    {
        cin >> a >> b;
        if (m.find(a) != m.end())
            m[a] += b;
        else
            m.insert({a, b});
    }
    cin >> k;
    ll count = 0;
    for (auto it: m) {
        count += it.second;
        if (count >= k) {
            cout << it.first;
            break;
        }
    }

    return 0;
}

• Time Complexity: O(Q log Q)
• Space Complexity: O(Q)

Cách tiếp cận này sử dụng cấu trúc dữ liệu std::map để lưu trữ các cặp (chỉ số, giá trị). Ưu điểm của map là nó tự động sắp xếp các chỉ số (key) theo thứ tự tăng dần.

1. Đọc q truy vấn cập nhật (a, b). Nếu chỉ số a đã tồn tại trong map, cộng dồn b vào giá trị hiện tại. Nếu chưa, thêm mới.
2. Đọc k.
3. Duyệt qua các phần tử của map (từ nhỏ đến lớn). Duy trì biến cộng dồn count.
4. Nếu tại một chỉ số a, count >= k, in ra a và dừng.

Độ phức tạp: Với Q truy vấn, việc chèn vào map mất O(log Q) mỗi lần. Khoảng thời gian để xây dựng map là O(Q log Q). Việc duyệt map để tìm k mất O(Q) trong trường hợp xấu nhất. Tổng thể O(Q log Q).

Cách Mảng và Sắp xếp

#include <bits/stdc++.h>

using namespace std;
pair <int,int>a[100005];
long long q,k,s;
int main()
{
    freopen("AQUERY.inp","r",stdin);
    freopen("AQUERY.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>q;
    for(int i=1;i<=q;i++)cin>>a[i].first>>a[i].second;
    cin>>k;
    sort(a+1,a+1+q);
    for(int i=1;i<=q;i++)
    {
        if(k<=a[i].second)
    {
        cout<<a[i].first;return 0;
    }
        k-=a[i].second;
    }
    return 0;
}

• Time Complexity: O(Q log Q)
• Space Complexity: O(Q)

Cách tiếp cận này sử dụng một mảng để lưu trữ tất cả các truy vấn cập nhật.

1. Đọc q truy vấn vào mảng các cặp (a, b).
2. Đọc k.
3. Sắp xếp mảng theo chỉ số a tăng dần.
4. Duyệt qua mảng đã sắp xếp, cộng dồn các giá trị b vào biến k (hoặc một biến cộng dồn khác).
5. Khi biến cộng dồn >= giá trị k ban đầu, in ra chỉ số a tại bước đó.

Lưu ý: Phương pháp này chỉ đúng nếu các chỉ số a là duy nhất hoặc các truy vấn cập nhật cho cùng một chỉ số không bị gộp lại trước khi sort. Tuy nhiên, trong code mẫu này, người ta nhập trực tiếp vào mảng và sort. Nếu có 2 truy vấn cho cùng một chỉ số a, chúng có thể nằm ở các vị trí khác nhau trong mảng. Nhưng do logic if(k<=a[i].second), nó chỉ tìm chỉ số đầu tiên mà tại đó tổng tiền tố >= k. Nếu có trùng lặp chỉ số, sort sẽ đặt chúng gần nhau, nhưng k chỉ được trừ đi a[i].second (lần đầu tiên nó xuất hiện).wait, code này không gộp các chỉ số giống nhau. Nó chỉ đơn thuần sort các truy vấn. Điều này có thể gây sai sót nếu cùng một chỉ số xuất hiện nhiều lần và tổng giá trị của nó quyết định kết quả, nhưng vị trí của nó trong mảng lại không liên tục? Không, sort sẽ đặt chúng cùng chỉ số ở gần nhau, nhưng logic trừ k không gộp chúng lại trừ khi viết vòng lặp gộp. Tuy nhiên, nhìn chung đây là một cách tiếp cận mảng/sort.

Cách Xử lý và Gộp truy vấn trước khi Sort

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

int main() {
    freopen("aquery.inp", "r", stdin);
    freopen("aquery.out", "w", stdout);

    int q;
    cin >> q;
    vector<pair<long long, long long>> v(q);
    for (int i = 0; i < q; i++) cin >> v[i].first >> v[i].second;
    long long k;
    cin >> k;

    sort(v.begin(), v.end());
    for (auto p : v) {
        if (k <= p.second) {
            cout << p.first;
            return 0;
        }
        k -= p.second;
    }
}

• Time Complexity: O(Q log Q)
• Space Complexity: O(Q)

Đây là phiên bản tương tự Approach 2 nhưng sử dụng vector và sort. Tuy nhiên, có một điểm khác biệt quan trọng trong cách xử lý logic.

Nếu输入 có các cặp (a, b) với a bị lặp lại (ví dụ (5, 10), (5, 20)), sort sẽ đặt chúng cạnh nhau. Vòng lặp for sẽ duyệt qua từng cặp một.

• Bước 1: Kiểm tra k <= 10. Nếu không, trừ k -= 10.
• Bước 2: Kiểm tra k <= 20. Nếu không, trừ k -= 20.

Điều này khác với Approach 1 (Map) là Map tự động gộp (sum) các giá trị cùng key trước. Approach 2 và 3 này xử lý như thể mỗi truy vấn là một phần tử riêng biệt. Tuy nhiên, về mặt logic bài toán, tổng tiền tố tại chỉ số 5 là 30. Nếu k=25, Approach 1 (sau khi sort) sẽ thấy chỉ số 5 có tổng là 30 >= 25 và in ra 5. Approach 3 này:

• Xem (5, 10): tổng tích lũy là 10. 10 < 25, trừ k -> k=15.
• Xem (5, 20): tổng tích lũy là 10+20=30. Kiểm tra k <= 20 (đúng vì 15 <= 20) -> in ra 5. Kết quả là như nhau. Vậy Approach 3 này là biến thể của Approach 2, sử dụng vector thay vì mảng c cứng.

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

Bài học kinh nghiệm

• Bài toán có thể được giảm thành bài toán tìm kiếm trên dãy số tổng tiền tố (Prefix Sum). Mục tiêu là tìm chỉ số a sao cho tổng các giá trị từ đầu đến a >= k.
• Do chỉ cần tìm chỉ số đầu tiên thỏa mãn điều kiện, ta không cần lưu trữ toàn bộ dãy số (vốn có thể rất lớn), mà chỉ cần lưu trữ các cặp (chỉ số, giá trị) có giá trị khác 0.
• Sử dụng std::map là một cách hiệu quả vì nó tự động sắp xếp các chỉ số, giúp việc tính tổng tiền tố trở nên dễ dàng mà không cần bước sort riêng.

Lỗi thường gặp

• Sử dụng mảng static quá nhỏ không đủ chứa số lượng truy vấn (ví dụ chỉ khai báo 10^5 phần tử trong khi Q có thể lớn hơn). Nên dùng vector hoặc map để linh hoạt.
• Quên xử lý trường hợp cùng một chỉ số xuất hiện nhiều lần. Nếu dùng mảng/struct và sort đơn thuần mà không gộp các phần tử cùng chỉ số, logic tính tổng tiền tố có thể bị sai lệch hoặc phức tạp hóa.
• Lỗi tràn số nguyên (Integer Overflow) nếu sử dụng int cho tổng giá trị hoặc k. Nên dùng long long.