Hướng giải của Số Màu Sắc Phân Biệ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 đếm số lượng phần tử phân biệt trong các đoạn con (Offline Queries):

  1. Ta lưu toàn bộ các truy vấn và sắp xếp chúng tăng dần theo đầu mút phải \(R\).
  2. Duyệt qua từng vị trí \(i\) từ \(1\) đến \(N\):
    • Nếu màu sắc \(a[i]\) đã từng xuất hiện ở vị trí last[a[i]] trước đó, ta loại bỏ đóng góp của vị trí cũ bằng cách cập nhật giảm 1 tại last[a[i]] trên Fenwick Tree.
    • Thêm đóng góp mới bằng cách cộng 1 tại vị trí \(i\) trên Fenwick Tree, và cập nhật last[a[i]] = i.
    • Khi vị trí duyệt đạt mút phải \(R\) của một truy vấn \([L, R]\), kết quả của truy vấn chính là: query(R) - query(L - 1).

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

Mã nguồn C++ mẫu

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

struct Query {
    int l, r, id;
    bool operator<(const Query& other) const { return r < other.r; }
};

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);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }
    sort(queries.begin(), queries.end());
    vector<int> bit(n + 2, 0);
    auto update = [&](int i, int val) {
        for (; i <= n; i += i & -i) bit[i] += val;
    };
    auto query = [&](int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    };
    vector<int> last(100005, 0);
    vector<int> ans(q);
    int r_idx = 1;
    for (int i = 0; i < q; i++) {
        while (r_idx <= queries[i].r) {
            if (last[a[r_idx]] != 0) {
                update(last[a[r_idx]], -1);
            }
            update(r_idx, 1);
            last[a[r_idx]] = r_idx;
            r_idx++;
        }
        ans[queries[i].id] = query(queries[i].r) - query(queries[i].l - 1);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
}

Nhận xét

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