Hướng giải của Giá Cổ Phiếu Lớn Nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu cập nhật điểm và truy vấn giá trị lớn nhất trên tiền tố \([1, R]\). Thông thường, Fenwick Tree không hỗ trợ trực tiếp các phép toán không có tính chất nghịch đảo (như max/min). Tuy nhiên, đối với truy vấn tiền tố (prefix query), ta hoàn toàn có thể duy trì được:

  • Hàm cập nhật giá trị tại vị trí \(pos\): Ta đi lên và cập nhật giá trị lớn nhất cho tất cả các nút chứa nó. Do là phép gán trị (có thể giảm), ta cần kết hợp kiểm tra cấu trúc nhánh.
  • Hàm truy vấn tiền tố \([1, R]\): Ta chỉ cần đi xuống theo chỉ số nhị phân và lấy giá trị cực đại của các nút quản lý.

Độ phức tạp thời gian: \(O(\log N)\) mỗi thao tác.

Mã nguồn C++ mẫu

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

int n, q;
vector<int> bit, a;

void update(int i, int val) {
    for (; i <= n; i += i & -i) bit[i] = max(bit[i], val);
}

int query(int i) {
    int res = 0;
    for (; i > 0; i -= i & -i) res = max(res, bit[i]);
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> q)) return 0;
    a.resize(n + 1);
    bit.assign(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        update(i, a[i]);
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int pos, val; cin >> pos >> val;
            a[pos] = val;
            int idx = pos;
            while (idx <= n) {
                bit[idx] = a[idx];
                int low = idx - (idx & -idx);
                for (int j = idx - 1; j > low; j -= j & -j) {
                    bit[idx] = max(bit[idx], bit[j]);
                }
                idx += idx & -idx;
            }
        } else {
            int r; cin >> r;
            cout << query(r) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.