Hướng giải của Số Thứ K Khác 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: Số Thứ K Khác Biệt

Phân tích bài toán
  1. Quy tắc chuyển trạng thái: Từ vị trí \(i\), tìm vị trí \(j > i\) nhỏ nhất sao cho đoạn con \(A[i..j-1]\) chứa đúng \(D\) phần tử phân biệt. Ta tìm mảng chuyển trạng thái nxt[i] = j bằng hai con trỏ kết hợp mảng đếm tần suất phần tử phân biệt trong cửa sổ trong \(O(N)\) thời gian.
  2. Tiền xử lý bảng Binary Lifting up[i][j] trong \(O(N \log N)\).
  3. Giải quyết mỗi truy vấn thực hiện nhảy đúng \(K\) bước trên đồ thị hàm số tĩnh trong \(O(\log K)\) thời gian.
Độ phức tạp
  • Thời gian: \(O(N \log K_{max})\) tiền xử lý và \(O(\log K)\) mỗi truy vấn.
  • Không gian: \(O(N \log K_{max})\) bộ nhớ.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q, d;
    if (!(cin >> n >> q >> d)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> vals = a;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    auto get_id = [&](int x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    };
    for (int i = 0; i < n; i++) a[i] = get_id(a[i]);

    vector<int> nxt(n + 1);
    nxt[n] = n;

    vector<int> freq(vals.size() + 2, 0);
    int distinct_count = 0;
    int r = 0;

    for (int i = 0; i < n; i++) {
        while (r < n && distinct_count < d) {
            freq[a[r]]++;
            if (freq[a[r]] == 1) {
                distinct_count++;
            }
            r++;
        }
        if (distinct_count >= d) {
            nxt[i] = r;
        } else {
            nxt[i] = n;
        }
        freq[a[i]]--;
        if (freq[a[i]] == 0) {
            distinct_count--;
        }
    }

    int LOG = 30;
    vector<vector<int>> up(n + 1, vector<int>(LOG));
    for (int i = 0; i <= n; i++) {
        up[i][0] = nxt[i];
    }
    for (int j = 1; j < LOG; j++) {
        for (int i = 0; i <= n; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    while (q--) {
        int u;
        long long k;
        cin >> u >> k;
        u--;
        for (int j = 0; j < LOG; j++) {
            if (k & (1LL << j)) {
                u = up[u][j];
            }
        }
        if (u == n) cout << -1 << "\n";
        else cout << u + 1 << "\n";
    }
    return 0;
}

Nhận xét

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