แบบสอบถามเกี่ยวกับการแทรกองค์ประกอบในลำดับ Bitonic ใน C++

ในปัญหานี้ เราได้รับคำสั่ง bitonic Sequence และ Q แต่ละแบบสอบถามมีจำนวนเต็ม x งานของเราคือการพิมพ์ความยาวของลำดับบิตโทนิกหลังจากใส่จำนวนเต็มหลังการสืบค้นแต่ละครั้ง และในตอนท้ายให้พิมพ์ลำดับบิตโทนิก

คำอธิบายปัญหา − ในที่นี้ เราได้รับลำดับบิตโทนิก และมีคิวรี Q ซึ่งแต่ละอันมีหนึ่งจำนวนเต็มที่จะเพิ่มลงในลำดับ เราจะเพิ่มองค์ประกอบจากการสืบค้นแต่ละครั้งไปยังลำดับ จากนั้นจึงคืนค่าความยาวของลำดับ 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.

เพื่อแก้ปัญหานี้ เราจะต้องแยกลำดับบิตโทนิกออกเป็นสองชุด ชุดหนึ่งเพื่อเพิ่มส่วนของลำดับให้มีค่าสูงสุด อีกอันหนึ่งสำหรับส่วนที่ลดลงของลำดับ

ตอนนี้ สำหรับทุกองค์ประกอบที่จะแทรก สามารถเป็นกรณีต่อไปนี้ -

กรณีที่ 1(หากองค์ประกอบมากกว่าค่าสูงสุด) − เพิ่มองค์ประกอบที่ส่วนท้ายของซีรีย์ที่เพิ่มขึ้น และอัปเดตสูงสุด

กรณีที่ 2 − หากองค์ประกอบน้อยกว่าค่าสูงสุด ให้เช็คอินชุดที่เพิ่มขึ้นก่อนสำหรับความพร้อมใช้งานขององค์ประกอบ แทรกหากไม่มีองค์ประกอบที่เท่ากับองค์ประกอบนั้น มิฉะนั้น ให้ค้นหาในชุดที่ลดลงและเพิ่มหากเป็นไปได้

กรณีที่ 3 (หากองค์ประกอบเท่ากับค่าสูงสุดหรือค่าที่มีอยู่ในชุดที่เพิ่มขึ้นและลดลง) − ปล่อยให้องค์ประกอบไม่สามารถเพิ่มได้

หลังจากการสืบค้นแต่ละครั้ง เราจะหาชุดของลำดับบิตโทนิกโดยการเพิ่มความยาวของทั้งสองชุด

length(bseq) = length(incSet) + length(decSet)

หลังจากเสร็จสิ้นการสืบค้นข้อมูลทั้งหมดแล้ว ให้พิมพ์ลำดับ bitonic โดยพิมพ์ theincSet แล้วพิมพ์ 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