আমাদের একটি Arr[] অ্যারে দেওয়া আছে যাতে পূর্ণসংখ্যা রয়েছে এবং একটি ২D অ্যারে Q যাতে কুয়েরি রয়েছে। প্রতিটি কুয়েরিতে ৩টি মান থাকে: lpos, rpos এবং K। ইনডেক্স i থেকে পরবর্তী ইনডেক্স i+1-এ একটি স্টেপে যাওয়া যায় অথবা সেই ইনডেক্সে থাকা যায়। lpos থেকে rpos-এ সর্বোচ্চ K স্টেপে যাওয়া যায়। প্রতিটি স্টেপে বামপাশের সংখ্যাও যোগ করে সমস্ত সংখ্যা যোগ করুন। লক্ষ্য হল সর্বোচ্চ K মুভে যোগফল সর্বাধিক করা। যদি lpos থেকে rpos-এ K স্টেপে যাওয়া সম্ভব না হয় তবে "No" প্রিন্ট করুন। আরও বুঝতে নিচে দেখুন।
বিভিন্ন ইনপুট-আউটপুট পরিস্থিতি দেখে নিই -
ইন - Arr[] = {1, 2, 4, -1 };
Q[][3] = { { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };
আউট -
Query 1: 7
Query 2: NO
Query 3: NO
Query 4: 11
ব্যাখ্যা -
প্রথম কুয়েরি:-
ইনডেক্স ০ থেকে ২-এ সর্বোচ্চ ২ স্টেপে যেতে পারি:-
স্টেপ ১:- ইনডেক্স ০ থেকে ১ ( 1+2=3 )
স্টেপ ২:- ইনডেক্স ১ থেকে ২ ( 3+4=7 )
দ্বিতীয় কুয়েরি:-
ইনডেক্স ০ থেকে ২-এ সর্বোচ্চ ১ স্টেপে যেতে পারি না। "NO" প্রিন্ট করুন
তৃতীয় কুয়েরি:-
ইনডেক্স ৩ থেকে ৩-এ সর্বোচ্চ ১ স্টেপে যেতে পারি না। "NO" প্রিন্ট করুন
চতুর্থ কুয়েরি:-
ইনডেক্স ০ থেকে ২-এ সর্বোচ্চ ৩ স্টেপে যেতে পারি:-
স্টেপ ১:- ইনডেক্স ০ থেকে ১ ( 1+2=3 )
স্টেপ ২:- ইনডেক্স ১ থেকে ২ ( 3+4=7 )
স্টেপ ৩:- ইনডেক্স ২-এ থাকুন ( 7+4=11 )
ইন - Arr[] = { 1, 2, 3, 3, 2 }; Q[][3] = { { 0, 3, 2 }, { 1, 4, 3 } };
আউট -
Query 1: NO
Query 2: 10
ব্যাখ্যা -
প্রথম কুয়েরি:-
ইনডেক্স ০ থেকে ২-এ সর্বোচ্চ ১ স্টেপে যেতে পারি না। "NO" প্রিন্ট করুন
দ্বিতীয় কুয়েরি:-
ইনডেক্স ১ থেকে ৪-এ সর্বোচ্চ ৩ স্টেপে যেতে পারি:-
স্টেপ ১:- ইনডেক্স ১ থেকে ২ ( 2+3=5 )
স্টেপ ২:- ইনডেক্স ২ থেকে ৩ ( 5+3=8 )
স্টেপ ৩:- ইনডেক্স ৩ থেকে ৪ ( 8+2=10 )
নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি
এই পদ্ধতিতে আমরা সেগমেন্ট ট্রি ব্যবহার করব lpos থেকে rpos রেঞ্জের জন্য সর্বোচ্চ মান খুঁজে বের করতে এবং প্রিফিক্স সম ব্যবহার করে সকল সংখ্যার যোগফল গণনা করব।
- ইনপুট অ্যারে Arr[] এবং কুয়েরি ম্যাট্রিক্স Q[][] নিন।
- sgTreee[5 * length] নিন সেগমেন্ট ট্রি ইমপ্লিমেন্ট করার জন্য অ্যারে হিসেবে।
- pSum[length] নিন প্রিফিক্স সম অ্যারে হিসেবে।
- createTree(int min, int max, int pos, int sgT[], int arr[], int len) ফাংশনটি সেগমেন্ট ট্রিতে মান তৈরি করতে ব্যবহৃত হয়।
- চেক করুন if (min == max) অর্থাৎ এটি একটি লীফ নোড। sgT[pos] = arr[max] সেট করুন।
- midd = (min + max) / 2 নিন।
- createTree(min, midd, loc1, sgT, arr, len) এবং createTree(midd + 1, max, loc2, sgT, arr, len) কল করুন বাম এবং ডান সাবট্রির জন্য যেখানে loc1=2*pos+1 এবং loc2=2*pos+2।
- tmp1=sgT[loc1] এবং tmp2=sgT[loc2] নিন এবং sgT[pos] আপডেট করুন tmp1 বা tmp2 যেটি সর্বোচ্চ।
- preSum(int pSum4[], int arr4[], int len4) ফাংশনটি ইনপুট অ্যারে নেয় এবং ফর লুপ ব্যবহার করে প্রিফিক্স অ্যারে আপডেট করে।
- ইনডেক্স ১ থেকে শেষ পর্যন্ত প্রতিটি উপাদানের জন্য, pSum4[j] = pSum4[j - 1] + arr4[j] আপডেট করুন।
- resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1) ফাংশনটি সকল ইনপুট প্যারামিটার নেয় এবং প্রতিটি কুয়েরির জন্য ফলাফল প্রিন্ট করে।
- resQuery()-র ভিতরে, solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) কল করুন ফর লুপ ব্যবহার করে প্রতিটি কুয়েরি আলাদা আলাদা সমাধান করতে।
- solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]) ফাংশনটি কুয়েরি সমাধান করে এবং ফলাফল রিটার্ন করে।
- যদি rpos - lpos > k তবে -1 রিটার্ন করুন কারণ কোনো সমাধান সম্ভব নয়।
- maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2) নিন।
- যদি maxVal < 0 তবে maxVal = 0 সেট করুন।
- sum = pSum2[rpos] ভেরিয়েবল নিন।
- যদি lpos > 0 তবে sum -= pSum2[lpos - 1] এবং result = sum + (k - (rpos - lpos)) * maxVal।
- result রিটার্ন করুন।
- findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1) ফাংশনটি lpos এবং rpos রেঞ্জের মাঝপথে সর্বোচ্চ মান রিটার্ন করে।
- যদি (min1 <= start) এবং (max1 >= end) তবে sgT1[pos1] রিটার্ন করুন কারণ ওভারল্যাপ আছে।
- যদি (end < min1 || start > max1) তবে আউট অফ রেঞ্জ ঘটছে তাই INT_MIN রিটার্ন করুন।
- লেফট এবং রাইট সাবট্রির জন্য রিকার্সিভ কল ব্যবহার করে lmax এবং rmax গণনা করুন এবং দুটির সর্বোচ্চ রিটার্ন করুন।
- শেষে প্রতিটি কুয়েরির জন্য ফলাফল প্রিন্ট হবে। "No" যদি কোনো সমাধান নেই।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void createTree(int min, int max, int pos, int sgT[], int arr[], int len){
if (min == max) {
sgT[pos] = arr[max];
return;
}
int midd = (min + max) / 2;
int loc1=2*pos+1;
int loc2=2*pos+2;
createTree(min, midd, loc1, sgT, arr, len);
createTree(midd + 1, max, loc2, sgT, arr, len);
int tmp1=sgT[loc1];
int tmp2=sgT[loc2];
sgT[pos] = tmp1>tmp2 ? tmp1 : tmp2 ;
}
int findMax(int start, int end, int min1, int max1, int pos1, int sgT1[], int arr1[], int len1){
int middle;
if (min1 <= start)
{ if( max1 >= end){
return sgT1[pos1];
}
}
if (end < min1 || start > max1)
{ return INT_MIN; }
middle = (start + end) / 2;
int loc1=2 * pos1 + 1;
int loc2=2 * pos1 + 2;
int lmax = findMax(start, middle, min1, max1, loc1, sgT1, arr1, len1);
int rmax = findMax(middle + 1, end, min1, max1, loc2, sgT1, arr1, len1);
int res=lmax>rmax?lmax:rmax;
return res;
}
int solQuery(int lpos, int rpos, int k, int len2, int arr2[], int sgT2[], int pSum2[]){
int result;
if (rpos - lpos > k)
{ return -1; }
int maxVal = findMax(0, len2 - 1, lpos, rpos, 0, sgT2, arr2, len2);
if (maxVal < 0)
{ maxVal = 0; }
int sum = pSum2[rpos];
if (lpos > 0)
{ sum -= pSum2[lpos - 1]; }
result = sum + (k - (rpos - lpos)) * maxVal;
return result;
}
void resQuery(int len3, int arr3[], int sgT3[], int pSum3[], int q1[][3], int qlen1){
int i;
int result;
for (i = 0; i < qlen1; i++) {
result = solQuery(q1[i][0], q1[i][1],q1[i][2], len3, arr3, sgT3, pSum3);
if (result == -1)
{ cout <<endl<<"Query "<<i+1<<": "<<"NO"; }
else
{ cout <<endl<<"Query "<<i+1<<": "<<result; }
}
}
void preSum(int pSum4[], int arr4[], int len4){
pSum4[0] = arr4[0];
int j;
for (j = 1; j < len4; j++){
pSum4[j] = pSum4[j - 1] + arr4[j];
}
}
int main(){
int Arr[] = {1, 2, 4, -1 };
int length = sizeof(Arr) / sizeof(Arr[0]);
int sgTreee[5 * length];
createTree(0, length - 1, 0, sgTreee, Arr, length);
int pSum[length];
preSum(pSum, Arr, length);
int Q[][3] = { { 0, 2, 2 }, { 0, 2, 1 }, { 3, 3, 1 }, { 0, 2, 3} };
int qlen = sizeof(Q) / sizeof(Q[0]);
resQuery(length, Arr, sgTreee, pSum, Q, qlen);
return 0;
}
আউটপুট
উপরোক্ত কোডটি রান করলে নিচের আউটপুটটি জেনারেট হবে
Query 1: 7 Query 2: NO Query 3: NO Query 4: 11
