Hướng giải của Tổng Trong Khoảng

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: Tổng Trong Khoảng

Phân tích bài toán

Yêu cầu thực hiện chèn, xóa và truy vấn tổng các phần tử có giá trị thuộc khoảng \([L, R]\).

Để thực hiện thao tác tính tổng trên khoảng giá trị lớn trực tiếp trực tuyến trong thời gian \(O(\log N)\), ta có thể sử dụng Augmented Skip List (mỗi liên kết lưu tổng giá trị các phần tử đi qua) hoặc cấu trúc cây Segment Tree/Treap động.

Tuy nhiên, do bài toán không yêu cầu truy vấn trực tuyến bắt buộc, ta có thể giải quyết offline bằng kỹ thuật Rời rạc hóa (Coordinate Compression) kết hợp với Cây chỉ số nhị phân (Binary Indexed Tree - Fenwick Tree):

  1. Đọc toàn bộ các phần tử ban đầu và tất cả các giá trị xuất hiện trong truy vấn (\(X, L, R\)).
  2. Sắp xếp và loại bỏ các giá trị trùng lặp để thu được danh sách các giá trị rời rạc hóa.
  3. Khi thực hiện truy vấn:
    • Thêm \(X\): Gọi update(get_id(x), x, 1).
    • Xóa \(X\): Gọi update(get_id(x), x, -1).
    • Tổng trong \([L, R]\): Gọi query(get_id(r)) - query(get_id(l) - 1).
Độ phức tạp
  • Thời gian: \(O((N + Q) \log(N + Q))\) cho thao tác rời rạc hóa và truy vấn BIT.
  • Không gian: \(O(N + Q)\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

struct Query {
    int type;
    long long x, l, r;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    if (!(cin >> n >> q)) return 0;
    vector<long long> a(n);
    vector<Query> queries(q);
    vector<long long> vals;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        vals.push_back(a[i]);
    }
    for (int i = 0; i < q; i++) {
        cin >> queries[i].type;
        if (queries[i].type == 1 || queries[i].type == 2) {
            cin >> queries[i].x;
            vals.push_back(queries[i].x);
        } else {
            cin >> queries[i].l >> queries[i].r;
            vals.push_back(queries[i].l);
            vals.push_back(queries[i].r);
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_id = [&](long long val) {
        return lower_bound(vals.begin(), vals.end(), val) - vals.begin() + 1;
    };

    int sz = vals.size();
    vector<long long> bit_sum(sz + 2, 0);

    auto update = [&](int idx, long long val, int cnt) {
        for (; idx <= sz; idx += idx & -idx) {
            bit_sum[idx] += val * cnt;
        }
    };

    auto query = [&](int idx, long long &sum_out) {
        sum_out = 0;
        for (; idx > 0; idx -= idx & -idx) {
            sum_out += bit_sum[idx];
        }
    };

    multiset<long long> s;
    for (int i = 0; i < n; i++) {
        s.insert(a[i]);
        update(get_id(a[i]), a[i], 1);
    }

    for (int i = 0; i < q; i++) {
        if (queries[i].type == 1) {
            long long x = queries[i].x;
            s.insert(x);
            update(get_id(x), x, 1);
        } else if (queries[i].type == 2) {
            long long x = queries[i].x;
            auto it = s.find(x);
            if (it != s.end()) {
                s.erase(it);
                update(get_id(x), x, -1);
            }
        } else {
            long long l = queries[i].l;
            long long r = queries[i].r;
            if (l > r) {
                cout << 0 << "\n";
                continue;
            }
            int id_l = get_id(l);
            int id_r = get_id(r);
            long long sum_r = 0, sum_l = 0;
            query(id_r, sum_r);
            query(id_l - 1, sum_l);
            cout << sum_r - sum_l << "\n";
        }
    }
    return 0;
}

Nhận xét

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