C++のBitonicシーケンスへの要素の挿入に関するクエリ

この問題では、バイトニックシーケンスとQクエリが与えられます。各クエリには整数xがあります。私たちのタスクは、各クエリの後に整数を挿入した後、バイトニックシーケンスの長さを出力することです。そして最後に、バイトニックシーケンスを印刷します。

問題の説明 −ここでは、バイトニックシーケンスが与えられています。また、Qクエリがあり、それぞれにシーケンスに追加される1つの整数が含まれています。各クエリの要素をシーケンスに追加してから、バイトニックシーケンスの長さを返します。すべてのクエリが完了したら、バイトニックシーケンスを出力します。

バイトニックシーケンス は特殊なタイプのシーケンスであり、あるポイント（バイトニックポイントと呼ばれる）まで増加し、その後減少します。

例-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。

この問題を解決するには、 ビットニックシーケンスを2つのセットに分割する必要があります。1つはシーケンスの一部を最大値まで増やすためのものです。もう1つは、シーケンスの減少部分用です。

さて、挿入されるすべての要素について、次の場合があります-

ケース1（要素が最大値より大きい場合） −増加するシリーズの最後に要素を追加し、最大値を更新します。

ケース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