সি++-এ L-তম ও R-তম স몰েস্ট সংখ্যার ইনডেক্স পার্থক্য বের করার কোয়েরি সমাধান

সমস্যা বিবরণ

একটি অ্যারে arr[] এবং Qটি কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে L এবং R থাকে। L-তম স্মলেস্ট এবং R-তম স্মলেস্ট উপাদানের ইনডেক্সের পরম পার্থক্য বের করতে হবে।

উদাহরণ: arr[] = {8, 4, 1, 5, 2}, Q = 2, Queries = {{2,4}, {1,5}}

আউটপুট: 1 2

ব্যাখ্যা:

• {2,4}: ২য় স্মলেস্ট = ২ (ইনডেক্স ৪), ৪র্থ স্মলেস্ট = ৫ (ইনডেক্স ৩) → পার্থক্য = ১
• {1,5}: ১ম স্মলেস্ট = ১ (ইনডেক্স ২), ৫ম স্মলেস্ট = ৮ (ইনডেক্স ০) → পার্থক্য = ২

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

1. pair অ্যারে তৈরি করুন যেখানে first = value, second = index।
2. এই অ্যারেটি ভ্যালু অনুযায়ী সর্ট করুন।
3. প্রতিটি কোয়েরির জন্য abs(sorted[L-1].second - sorted[R-1].second) ক্যালকুলেট করুন।
4. O(n log n + Q) টাইম কমপ্লেক্সিটি।

উদাহরণ কোড

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

void solveAllQueries(int arr[], int n, int Q, int queries[][2]) {
    pair<int, int> arrayIndex[n];
    for (int i = 0; i < n; i++) {
        arrayIndex[i].first = arr[i];
        arrayIndex[i].second = i;
    }
    sort(arrayIndex, arrayIndex + n);
    for (int i = 0; i < Q; i++) {
        int result = abs(arrayIndex[queries[i][0]-1].second - arrayIndex[queries[i][1]-1].second);
        cout << "For Query " << (i+1) << ": Difference is " << result << endl;
    }
}

int main() {
    int arr[] = {8, 4, 1, 5, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int Q = 2;
    int queries[][2] = {{2,4}, {1,5}};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

আউটপুট

For Query 1: Difference is 1
For Query 2: Difference is 2