আমাদের কাছে একটি ইন্টিজার অ্যারে, সেগমেন্টের স্টার্ট এবং এন্ড পয়েন্টার সেট এবং একটি কি ভ্যালু আছে, এবং এখানে সমস্যা হলো দেওয়া রেঞ্জে যে সকল মান দিয়ে गये কি ভ্যালুর চেয়ে ছোট বা সমান সেগুলো খুঁজে বের করা।
উদাহরণ দিয়ে বুঝি
ইনপুট − arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }
সেগমেন্ট ১: start = 2, end = 4, k = 2
সেগমেন্ট ২: start = 1, end = 6, k = 3
আউটপুট − দিয়ে गये রেঞ্জে কি ভ্যালুর চেয়ে ছোট বা সমান সংখ্যার কাউন্ট: 2 6
ব্যাখ্যা − [8, 1, 4] ২ থেকে ৪ রেঞ্জ প্রতিনিধিত্ব করে এবং ২ হলো এই রেঞ্জে ২য় সবচেয়ে ছোট সংখ্যা [7, 8 , 1, 4 , 6 , 8 ] ১ থেকে ৬ রেঞ্জ প্রতিনিধিত্ব করে এবং ৬ হলো এই রেঞ্জে ৩য় সবচেয়ে ছোট সংখ্যা
ইনপুট − arr[] = {2, 7 , 9, 4 , 6 , 5 , 1 }
সেগমেন্ট ১: start = 3, end = 6, k = 4
সেগমেন্ট ২: start = 2, end = 5, k = 3
আউটপুট − দিয়ে गये রেঞ্জে কি ভ্যালুর চেয়ে ছোট বা সমান সংখ্যার কাউন্ট: 9 7
ব্যাখ্যা − [9, 4 , 6 , 5] ৩ থেকে ৬ রেঞ্জ প্রতিনিধিত্ব করে এবং ৯ হলো এই রেঞ্জে ৪র্থ সবচেয়ে ছোট সংখ্যা [7 , 9, 4 , 6 ] ২ থেকে ৪ রেঞ্জ প্রতিনিধিত্ব করে এবং ৭ হলো এই সেগমেন্ট রেঞ্জে ৩য় সবচেয়ে ছোট সংখ্যা
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি −
ইন্টিজার টাইপ অ্যারে ডিক্লেয়ার। অ্যারের আকার হিসাব। ইন্টিজার টাইপের পেয়ার বানানো ভেক্টর ভেরিয়েবল। FOR লুপ চালিয়ে অ্যারে থেকে ভেক্টরে ডেটা পুশ।
দেওয়া ভেক্টর সর্ট। MAX সাইজের ইন্টিজার টাইপ ভেক্টর অ্যারে তৈরি।
generateTree(1, 0, size - 1, vec, tree) ফাংশন কল এবং getSmallestIndex = queryWrapper(2, 5, 2, size, vec, tree) সেট।
input[getSmallestIndex] প্রিন্ট।
getSmallestIndex = queryWrapper(1, 6, 4, size, vec, tree) ফাংশন কল।
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]) ফাংশনের ভিতরে
চেক IF leftIndex == rightIndex তবে tree[treeIndex].push_back(a[leftIndex].second) এবং রিটার্ন
midValue = (leftIndex + rightIndex) / 2 সেট এবং generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) এবং merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])) কল
int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[]) ফাংশনের ভিতরে
চেক IF startIndex == endIndex তবে tree[treeIndex][0] রিটার্ন
mid = (startIndex + endIndex) / 2, last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin()) সেট
first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) এবং M = last_in_query_range - first_in_query_range সেট
চেক IF M >= key তবে calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree) রিটার্ন
ELSE, calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree) রিটার্ন।
int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int> > &a, vector<int> tree[]) ফাংশনের ভিতরে
calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree) কল রিটার্ন
উদাহরণ
#include <bits/stdc++.h> using namespace std; const int MAX = 1000; void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){ if (leftIndex == rightIndex){ tree[treeIndex].push_back(a[leftIndex].second); return; } int midValue = (leftIndex + rightIndex) / 2; generateTree(2 * treeIndex, leftIndex, midValue, a, tree); generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree); merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(), tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])); } int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){ if (startIndex == endIndex){ return tree[treeIndex][0]; } int mid = (startIndex + endIndex) / 2; int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin()); int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()); int M = last_in_query_range - first_in_query_range; if (M >= key){ return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree); } else { return calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree); } } int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int> > &a, vector<int> tree[]){ return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree); } int main(){ int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 }; int size = sizeof(input)/sizeof(input[0]); vector<pair<int, int> > vec; for (int i = 0; i < size; i++) { vec.push_back(make_pair(input[i], i)); } sort(vec.begin(), vec.end()); vector<int> tree[MAX]; generateTree(1, 0, size - 1, vec, tree); cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl; int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree); cout << input[getSmallestIndex] << endl; getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree); cout << input[getSmallestIndex] << endl; return 0; }
আউটপুট
উপরের কোড রান করলে নিচের আউটপুট জেনারেট হবে
Count of number which are smaller than or equal to key value in the given range are: 4 6
