Hướng giải của Quản Lý Mức Lươ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

Do giá trị mức lương lên tới \(10^9\), ta thực hiện Nén tọa độ (Coordinate Compression) tất cả các giá trị xuất hiện trong mảng ban đầu và các truy vấn:

  1. Gom toàn bộ các giá trị mức lương ban đầu và mức lương thay đổi, các cận min_val, max_val của truy vấn, sắp xếp và xóa trùng lặp.
  2. Dùng cây Fenwick Tree quản lý số lượng nhân viên đạt mức lương tương ứng sau khi nén.
  3. Khi thay đổi lương của một nhân viên từ \(old\) sang \(new\):
    • Trừ 1 tại vị trí nén của \(old\) trên Fenwick Tree.
    • Cộng 1 tại vị trí nén của \(new\) trên Fenwick Tree.
  4. Đếm số nhân viên trong khoảng \([min, max]\) bằng query(compressed_max) - query(compressed_min - 1).

Độ phức tạp thời gian: \(O((N + Q) \log(N + Q))\).

Mã nguồn C++ mẫu

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

struct Query {
    int t; int pos; int val; int min_val; int max_val;
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; if (!(cin >> n >> q)) return 0;
    vector<int> a(n + 1);
    vector<int> vals;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        vals.push_back(a[i]);
    }
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].t;
        if (queries[i].t == 1) {
            cin >> queries[i].pos >> queries[i].val;
            vals.push_back(queries[i].val);
        } else {
            cin >> queries[i].min_val >> queries[i].max_val;
            vals.push_back(queries[i].min_val);
            vals.push_back(queries[i].max_val);
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto get_compressed = [&](int v) {
        return lower_bound(vals.begin(), vals.end(), v) - vals.begin() + 1;
    };
    int m = vals.size();
    vector<int> bit(m + 2, 0);
    auto update = [&](int i, int val) {
        for (; i <= m; i += i & -i) bit[i] += val;
    };
    auto query = [&](int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };
    for (int i = 1; i <= n; i++) {
        update(get_compressed(a[i]), 1);
    }
    for (int i = 0; i < q; i++) {
        if (queries[i].t == 1) {
            update(get_compressed(a[queries[i].pos]), -1);
            a[queries[i].pos] = queries[i].val;
            update(get_compressed(a[queries[i].pos]), 1);
        } else {
            int l_idx = get_compressed(queries[i].min_val);
            int r_idx = get_compressed(queries[i].max_val);
            cout << query(r_idx) - query(l_idx - 1) << "\n";
        }
    }
}

Nhận xét

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