এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার আকার n এবং একটি কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে দুটি মান (L, R) থাকে। আমাদের কাজ হলো সাবঅ্যারেতে স্বতন্ত্র এলিমেন্টের সংখ্যা বের করার প্রোগ্রাম লিখা।
সমস্যা বর্ণনা − এখানে আমাদেরকে (L-1) থেকে (R-1) ইনডেক্স পর্যন্ত সাবঅ্যারেতে কতগুলো স্বতন্ত্র পূর্ণসংখ্যা আছে তা বের করতে হবে।
উদাহরণ দিয়ে বুঝি,
ইনপুট
arr[] = {4, 6, 1, 3, 1, 6, 5}
query = [1, 4]আউটপুট
4
ব্যাখ্যা
কোয়েরি ১: L = 1 এবং R = 4, ইনডেক্স ০ থেকে ৩ পর্যন্ত স্বতন্ত্র এলিমেন্টের সংখ্যা ৪।
কোয়েরি ২: L = 2 এবং R = 6, ইনডেক্স ১ থেকে ৫ পর্যন্ত স্বতন্ত্র এলিমেন্টের সংখ্যা ৩।
সমাধান পদ্ধতি
প্রতিটি কোয়েরি সমাধানের একটি সহজ পদ্ধতি হচ্ছে L থেকে R পর্যন্ত অ্যারে ট্রাভার্স করে এলিমেন্টগুলো সেটে রাখা, যেকারন সেটের আকার স্বতন্ত্র এলিমেন্টের সংখ্যা দেবে। এই পদ্ধতিটি আগের সেটে আলোচনা করা হয়েছে।
একটি আরও কার্যকর পদ্ধতি হচ্ছে সেগমেন্ট টรี ডেটা স্ট্রাকচার ব্যবহার করা। এটি দেওয়া রেঞ্জের স্বতন্ত্র এলিমেন্ট কাউন্ট সংরক্ষণ করে।
একটি সেগমেন্ট ট్రీ হলো একটি বিশেষ ধরনের ট্রি, যা সেগমেন্ট আকারে তথ্য সংরক্ষণ করে।
সেগমেন্ট ট্রির লিফ নোডগুলো অ্যারের এলিমেন্টগুলো নির্দেশ করে। আর নন-লিফ নোডগুলো সেগমেন্টগুলো এবং அவশ্যক মান সংরক্ষণ করে। এখানে এটি স্বতন্ত্র এলিমেন্টগুলো সংরক্ষণ করবে। এই ডেটা স্ট্রাকচার ইমপ্লিমেন্টেশনের জন্য আমরা সেট ব্যবহার করব।
উপরের সমাধানের ইমপ্লিমেন্টেশন −
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
set<int>* segmentTree;
void CreateSegmentTree(int i, int s, int e, int arr[]) {
if (s == e) {
segmentTree[i].insert(arr[s]);
return;
}
CreateSegmentTree(2 * i, s, (s + e) / 2, arr);
CreateSegmentTree(1 + 2 * i, 1 + (s + e) / 2, e, arr);
segmentTree[i].insert( segmentTree[2 * i].begin(), segmentTree[2 * i].end());
segmentTree[i].insert(segmentTree[2 * i + 1].begin(), segmentTree[2 * i + 1].end());
}
set<int> findDistSubarray(int node, int l, int r, int a, int b) {
set<int> left, right, distinctSubarray;
if (b < l || a > r)
return distinctSubarray;
if (a <= l && r <= b)
return segmentTree[node];
left = findDistSubarray(2 * node, l, (l + r) / 2, a, b);
distinctSubarray.insert(left.begin(), left.end());
right = findDistSubarray(1 + 2 * node, 1 + (l + r) / 2, r, a, b);
return distinctSubarray;
}
int main() {
int arr[] = {4, 6, 1, 3, 1, 6, 5};
int n = sizeof(arr) / sizeof(arr[0]);
int query[] = {1, 4};
int i = (int)ceil(log2(n));
i = (2 * (pow(2, i))) - 1;
segmentTree = new set<int>[i];
CreateSegmentTree(1, 0, n - 1, arr);
set<int> distCount = findDistSubarray(1, 0, n - 1, (query[0]-1), (query[1]-1));
cout<<"The number of distinct elements in the subarray is "<<distCount.size();
return 0;
}আউটপুট
The number of distinct elements in the subarray is 4
