在C ++中的双音序列中插入元素的查询
在这个问题上，我们得到了双音序列和Q查询。每个查询都有一个整数x。我们的任务是在每个查询之后插入整数后打印双音序列的长度。最后打印双音序列。
问题描述-在这里，我们得到了一个双音序列。有Q个查询，每个查询包含一个要添加到序列中的整数。我们将每个查询的元素添加到序列中，然后返回双音序列的长度。完成所有查询后，我们将打印双音序列。
重音序列是一种特殊的序列，它先增大到一个点（称为重音点），然后减小。
示例-1，5，6，8，9，9，7，5
让我们举个例子来更好地理解问题，
输入项
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 }输出结果
7 7
{1, 4, 5, 6, 5, 2, 1 }说明
对于第一个查询，要插入的值为5，可以将其插入序列长度为7的序列{1、4、5、6、5、2、1}的递增部分中。
对于第一个查询，要插入的值为6，不能插入，因为6是最大值。因此，将不会插入6。
最终序列{1，4，5，6，5，2，1}长7。
为了解决这个问题，我们必须将双音序列分成两组，一组将序列的一部分增加到最大值。另一个用于序列的递减部分。
现在，对于要插入的每个元素，可以是以下情况-
情况1（如果元素大于max）-在递增序列的末尾添加元素，并更新max。
情况2- 如果元素小于最大值，则首先检入递增集以了解元素的可用性，如果没有等于它的元素，则插入。否则，请搜索递减集并在可能的情况下添加。
情况3（如果元素等于max或该值在递增和递减集中均可用）-离开该元素将无法添加。
每次查询操作之后，我们将通过添加两个序列的长度来找到双音序列的集合，
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