โปรแกรมตอบคำถามจำนวนจำนวนเต็มที่ไม่ซ้ำใน Suffix ใน C++

ให้อาร์เรย์ arr[] ขนาด n และ Q คำถาม แต่ละคำถามมี k ต้องการหาจำนวนค่าที่ไม่ซ้ำใน arr[k..n-1] (1-indexed)

ตัวอย่าง: arr = [5,1,2,1,6,5], queries = {1,3,4} k=1: [5,1,2,1,6,5] → {5,1,2,6} = 4 k=3: [2,1,6,5] → {2,1,6,5} = 4 k=4: [1,6,5] → {1,6,5} = 3

วิธีแก้ปัญหาที่มีประสิทธิภาพ

คำนวณล่วงหน้า (Precompute) จากท้ายมาหน้า ใช้ unordered_set เก็บค่าที่เจอแล้ว distIntCount[i] = จำนวนค่าที่ไม่ซ้ำจาก i ถึง n-1

ตัวอย่างโค้ด C++

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

void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
    unordered_set<int> uniqueInts;
    int distIntCount[n+1];
    for (int i = n-1; i >= 0; i--) {
        uniqueInts.insert(arr[i]);
        distIntCount[i+1] = uniqueInts.size(); // 1-indexed
    }
    for (int i = 0; i < Q; i++)
        cout << "Query " << i+1 << ": " << distIntCount[queries[i]] << '\n';
}

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;
}

เอาต์พุต

Query 1: 4
Query 2: 4
Query 3: 3