সি++-এ সাফিক্সে স্বতন্ত্র ইন্টিজার সংখ্যা গণনার কোয়েরি সমাধান

সমস্যা বিবরণ

একটি অ্যারে arr[] এবং Qটি কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে একটি ইন্টিজার k থাকে। k-থেকেই n- পর্যন্ত সাফিক্সে কতগুলো স্বতন্ত্র (distinct) ইন্টিজার আছে তা বের করতে হবে। অ্যারে ১-ইনডেক্সড।

উদাহরণ: arr = {5,1,2,1,6,5}, n=6, Q=3, queries = {1,3,4}

আউটপুট: 4, 4, 3

সমাধানের পদ্ধতি

ইফিশিয়েন্ট সমাধান (পূর্ব-গণনা):

1. একটি unordered_set এবং distIntCount[] অ্যারে ব্যবহার করুন।
2. অ্যারেকে পিছন থেকে সামনে ট্রভার্স করুন (n-1 থেকে 0)।
3. প্রতিটি উপাদান সেটে ইনসার্ট করুন, distIntCount[i+1] = set.size()।
4. প্রতিটি কোয়েরি O(1) সময়ে distIntCount[k] দিয়ে উত্তর দিন।

উদাহরণ কোড

#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();
    }
    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[n] = {5, 1, 2, 1, 6, 5};
    int queries[Q] = {1, 3, 4};
    solveQueries_DistInt(n, arr, Q, queries);
    return 0;
}

আউটপুট

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