इस प्रॉब्लम में हमें bitonic Sequence और Q query दिए जाते हैं। प्रत्येक क्वेरी में एक पूर्णांक x होता है। हमारा काम प्रत्येक क्वेरी के बाद पूर्णांक डालने के बाद बिटोनिक अनुक्रम की लंबाई को प्रिंट करना है। और अंत में बिटोनिक अनुक्रम प्रिंट करें।
समस्या का विवरण - यहां, हमें एक बिटोनिक अनुक्रम दिया गया है। और क्यू प्रश्न हैं, प्रत्येक में एक पूर्णांक है जिसे अनुक्रम में जोड़ा जाना है। हम प्रत्येक क्वेरी से अनुक्रम में तत्व जोड़ेंगे और फिर बिटोनिक अनुक्रम की लंबाई वापस कर देंगे। सभी क्वेरी पूरी होने के बाद, हम बिटोनिक अनुक्रम को प्रिंट करेंगे।
बिटोनिक अनुक्रम एक विशेष प्रकार का अनुक्रम है, जो एक बिंदु तक बढ़ता है (जिसे बिटोनिक बिंदु कहा जाता है), और फिर घट जाता है।
उदाहरण - 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 } स्पष्टीकरण
पहली क्वेरी के लिए, डाला जाने वाला मान 5 है जिसे अनुक्रम के बढ़ते भाग में डाला जा सकता है {1, 4, 5, 6, 5, 2, 1}, लंबाई 7.
पहली क्वेरी के लिए, डाला जाने वाला मान 6 है जिसे डाला नहीं जा सकता क्योंकि 6 अधिकतम मान है। तो, 6 नहीं डाला जाएगा।
अंतिम क्रम {1, 4, 5, 6, 5, 2, 1} लंबाई 7.
इस समस्या को हल करने के लिए, हमें बिटोनिक अनुक्रम को दो सेटों में विभाजित करना होगा, एक अनुक्रम के हिस्से को अधिकतम मूल्य तक बढ़ाने के लिए। अनुक्रम के घटते भाग के लिए दूसरा।
अब, प्रत्येक तत्व को सम्मिलित करने के लिए निम्नलिखित मामले हो सकते हैं -
केस 1(यदि तत्व अधिकतम से बड़ा है) - बढ़ती श्रृंखला के अंत में तत्व जोड़ें, और अधिकतम अपडेट करें।
केस 2 - यदि तत्व अधिकतम से कम है, तो तत्व की उपलब्धता के लिए बढ़ते सेट में पहले चेक-इन करें, यदि इसके बराबर कोई तत्व उपलब्ध नहीं है तो डालें। अन्यथा, घटते हुए सेट में खोजें और यदि संभव हो तो जोड़ें।
केस 3 (यदि तत्व अधिकतम के बराबर है या मान बढ़ते और घटते दोनों सेट में उपलब्ध है) - छोड़ दें तत्व जोड़ा नहीं जा सकता।
प्रत्येक क्वेरी ऑपरेशन के बाद, हम दोनों सेटों की लंबाई जोड़कर बिटोनिक अनुक्रम का सेट पाएंगे,
length(bseq) = length(incSet) + length(decSet)
सभी प्रश्नों के होने के बाद, 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