Truy vấn số số nguyên khác biệt trong hậu tố trong C++

Mô tả bài toán

Cho mảng arr[] kích thước n và Q truy vấn mỗi truy vấn một chỉ số k (1-based). Tìm số lượng phần tử khác biệt trong đoạn arr[k..n].

Ví dụ: arr = [5,1,2,1,6,5], truy vấn {1,3,4} → 4, 4, 3.

Giải pháp hiệu quả

Duyệt từ phải sang trái, dùng unordered_set để lưu các giá trị đã thấy. Tại vị trí i, số lượng phần tử khác biệt từ i đến n chính là kích thước set. Lưu vào mảng distIntCount[i+1]. Trả lời truy vấn O(1).

Ví dụ minh họa (C++)

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

void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
    unordered_set<int> uniqueInts;
    vector<int> distIntCount(n+1);
    for (int i = n-1; i >= 0; i--) {
        uniqueInts.insert(arr[i]);
        distIntCount[i+1] = uniqueInts.size();
    }
    for (int i = 0; i < Q; i++)
        cout << "For Query " << (i+1) << ": the number of distinct integers in Suffix is " << distIntCount[queries[i]] << endl;
}

int main() {
    int n = 6, Q = 3;
    int arr[] = {5,1,2,1,6,5};
    int queries[] = {1,3,4};
    solveQueries_DistInt(n, arr, Q, queries);
    return 0;
}

Đầu ra

For Query 1: the number of distinct integers in Suffix is 4
For Query 2: the number of distinct integers in Suffix is 4
For Query 3: the number of distinct integers in Suffix is 3