이 문제에서는 bitonic Sequence 및 Q 쿼리가 제공됩니다. 각 쿼리에는 정수 x가 있습니다. 우리의 임무는 각 쿼리 뒤에 정수를 삽입한 후 비트 시퀀스의 길이를 출력하는 것입니다. 그리고 마지막에 bitonic sequence를 출력합니다.
문제 설명 − 여기에서 우리는 bitonic 시퀀스를 받습니다. 그리고 각각 시퀀스에 추가될 하나의 정수를 포함하는 Q 쿼리가 있습니다. 각 쿼리의 요소를 시퀀스에 추가한 다음 bitonic 시퀀스의 길이를 반환합니다. 모든 쿼리가 완료되면 bitonic 시퀀스를 인쇄합니다.
바이토닉 시퀀스 특정 유형의 시퀀스로, 포인트(비트닉 포인트라고 함)까지 증가했다가 감소합니다.
예 - 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.
이 문제를 해결하려면 우리는 bitonic 시퀀스를 두 개의 세트로 분할해야 합니다. 하나는 시퀀스의 일부를 최대값까지 증가시키기 위한 것입니다. 시퀀스의 감소 부분에 대한 다른 하나입니다.
이제 삽입할 모든 요소에 대해 다음과 같은 경우가 될 수 있습니다. -
사례 1(요소가 최대값보다 큰 경우) - 증가하는 계열의 끝에 요소를 추가하고 최대값을 업데이트합니다.
사례 2 - 요소가 최대값보다 작으면 요소의 가용성을 위해 증가하는 세트를 먼저 체크인하고, 사용 가능한 요소와 동일한 요소가 없으면 삽입합니다. 그렇지 않으면 감소 집합에서 검색하고 가능한 경우 추가합니다.
케이스 3(요소가 최대값과 같거나 값이 증가 및 감소 세트 모두에서 사용 가능한 경우) - 요소를 추가할 수 없습니다.
각 쿼리 작업 후에 두 집합의 길이를 더하여 비트 시퀀스 집합을 찾습니다.
length(bseq) = length(incSet) + length(decSet)
모든 쿼리가 완료되면 incSet을 인쇄한 다음 decSet을 인쇄하여 bitonic 시퀀스를 인쇄하십시오.
우리 솔루션의 작동을 설명하는 프로그램 −
예시
#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