समस्या विवरण
इस समस्या में, हमें एक बिटोनिक अनुक्रम (Bitonic Sequence) और Q क्वेरीज़ दी गई हैं। प्रत्येक क्वेरी में एक पूर्णांक 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 calcBitonicSeqLength(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 << "क्वेरी " << (i+1) << ": बिटोनिक अनुक्रम की लंबाई " << length << endl;
}
cout << "सभी क्वेरीज़ के अंत में बिटोनिक अनुक्रम: ";
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 };
calcBitonicSeqLength(bSeq, n, query, Q);
return 0;
}
आउटपुट
क्वेरी 1: बिटोनिक अनुक्रम की लंबाई 6 क्वेरी 2: बिटोनिक अनुक्रम की लंबाई 7 सभी क्वेरीज़ के अंत में बिटोनिक अनुक्रम: 1 4 5 6 5 2 1
