এই সমস্যাতে, আমাদের একটি বিটোনিক সিকোয়েন্স এবং Q সংখ্যক কোয়েরি দেওয়া আছে। প্রতিটি কোয়েরিতে একটি পূর্ণসংখ্যা x থাকে। আমাদের কাজ হলো প্রতিটি কোয়েরি প্রক্রিয়া করার পর বিটোনিক সিকোয়েন্সের দৈর্ঘ্য প্রিন্ট করা এবং সব কোয়েরি শেষে ফাইনাল বিটোনিক সিকোয়েন্সটি প্রিন্ট করা।
সমস্যা বর্ণনা − এখানে একটি বিটোনিক সিকোয়েন্স দেওয়া আছে। Q সংখ্যক কোয়েরি আছে, প্রতিটিতে একটি পূর্ণসংখ্যা যা সিকোয়েন্সে যোগ করতে হবে। আমরা প্রতিটি কোয়েরির এলিমেন্ট সিকোয়েন্সে যোগ করব এবং বিটোনিক সিকোয়েন্সের দৈর্ঘ্য রিটার্ন করব। সব কোয়েরি শেষে বিটোনিক সিকোয়েন্সটি প্রিন্ট করব।
বিটোনিক সিকোয়েন্স হলো একটি বিশেষ ধরনের সিকোয়েন্স, যা একটি নির্দিষ্ট বিন্দু (বিটোনিক পয়েন্ট) পর্যন্ত বাড়ে এবং তারপর কমে।
উদাহরণ − 1, 5, 6, 8, 9, 7, 5, 2
উদাহরণ দিয়ে বুঝি,
ইনপুট
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 }আউটপুট
7 7
{1, 4, 5, 6, 5, 2, 1 }ব্যাখ্যা
প্রথম কোয়েরিতে ইনসার্ট করার মান ৫, যা ক্রমবর্ধমান অংশে যোগ করা যায়, সিকোয়েন্স হয় {1, 4, 5, 6, 5, 2, 1 }, দৈর্ঘ্য ৭।
দ্বিতীয় কোয়েরিতে মান ৬, যা সর্বোচ্চ মান, তাই এটি যোগ করা যায় না।
ফাইনাল সিকোয়েন্স {1, 4, 5, 6, 5, 2, 1 } দৈর্ঘ্য ৭।
সমাধান পদ্ধতি: বিটোনিক সিকোয়েন্সকে দুটি সেটে ভাগ করতে হবে − একটি ক্রমবর্ধমান অংশের জন্য (সর্বোচ্চ মান পর্যন্ত) এবং অন্যটি ক্রমহ্রাসমান অংশের জন্য।
প্রতিটি ইনসার্ট করার এলিমেন্টের জন্য নিচের কেসগুলো হতে পারে −
কেস ১ (যদি এলিমেন্ট সর্বোচ্চ মানের চেয়ে বড় হয়) − ক্রমবর্ধমান সেটের শেষে এলিমেন্টটি যোগ করুন এবং সর্বোচ্চ মান আপডেট করুন।
কেস ২ − যদি এলিমেন্ট সর্বোচ্চ মানের চেয়ে ছোট হয়, প্রথমে ক্রমবর্ধমান সেটে চেক করুন যে সেটি আছে কিনা। যদি না থাকে তবে যোগ করুন। অন্যথায় ক্রমহ্রাসমান সেটে চেক করুন এবং সম্ভব হলে যোগ করুন।
কেস ৩ (যদি এলিমেন্ট সর্বোচ্চ মানের সমান হয় বা দুটি সেটে উভয়েই থাকে) − এলিমেন্টটি যোগ করা যাবে না।
প্রতিটি কোয়েরি অপারেশনের পর, বিটোনিক সিকোয়েন্সের দৈর্ঘ্য = incSet.size() + decSet.size()।
সব কোয়েরি শেষে incSet এবং decSet (রিভার্স অর্ডারে) প্রিন্ট করে বিটোনিক সিকোয়েন্স বের করুন।
সমাধানের কোড উদাহরণ −
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
int maxVal = INT_MIN;
for (int i = 0; i < n; i++)
maxVal = max(maxVal, bSeq[i]);
set <int> incSet, decSet;
incSet.insert(bSeq[0]);
decSet.insert(bSeq[n - 1]);
for (int i = 1; i < n; i++)
if (bSeq[i] > bSeq[i - 1])
incSet.insert(bSeq[i]);
for (int i = n - 2; i >= 0; i--)
if (bSeq[i] > bSeq[i + 1])
decSet.insert(bSeq[i]);
decSet.erase(decSet.find(maxVal));
for (int i = 0; i < Q; i++) {
if (maxVal <= query[i]) {
maxVal = query[i];
incSet.insert(query[i]);
}
else {
if (incSet.find(query[i]) == incSet.end())
incSet.insert(query[i]);
else
decSet.insert(query[i]);
}
int length = incSet.size() + decSet.size();
cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
}
cout<<"The Bitonic Sequence at the end of all queries is : ";
set<int>::iterator it;
for (it = incSet.begin(); it != incSet.end(); it++)
cout<<(*it)<<" ";
set<int>::reverse_iterator revIt;
for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
cout<<(*revIt)<<" ";
}
int main(){
int bSeq[] = { 1, 4, 6, 5, 2, 1 };
int n = sizeof(bSeq) / sizeof(bSeq[0]);
int Q = 2;
int query[] = { 6, 5 };
calcBitonicSeqLenth(bSeq, n, query, Q);
return 0;
}আউটপুট
For query 1: The length of Bitonic Sequence is 6 For query 2: The length of Bitonic Sequence is 7 The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1
