การสืบค้นการแทรกค่าในลำดับ Bitonic ใน C++

ในปัญหานี้ เราได้รับลำดับ Bitonic (ลำดับที่เพิ่มขึ้นจนถึงจุดสูงสุด แล้วค่อยลดลง) และ Q queries แต่ละ query มีค่าจำนวนเต็ม x ภารกิจคือการพิมพ์ความยาวของลำดับ Bitonic หลังจากแทรกจำนวนเต็มจากแต่ละ query และในที่สุดพิมพ์ลำดับ Bitonic ที่ได้

คำอธิบายปัญหา

เราได้รับลำดับ Bitonic และมี Q queries แต่ละ query มีจำนวนเต็มหนึ่งค่าที่จะนำไปเพิ่มในลำดับ เราจะเพิ่มค่าจากแต่ละ query เข้าไปในลำดับ แล้วคืนค่าความยาวของลำดับ Bitonic หลังจากเสร็จสิ้นทุก queries เราจะพิมพ์ลำดับ Bitonic ออกมา

ลำดับ Bitonic คือลำดับพิเศษที่ค่าขององค์ประกอบเพิ่มขึ้นจนถึงจุดหนึ่ง (เรียกว่า Bitonic point) แล้วค่อยลดลง

ตัวอย่าง: 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}

คำอธิบาย

สำหรับ query แรก ค่าที่จะแทรกคือ 5 ซึ่งสามารถแทรกในส่วนที่เพิ่มขึ้นของลำดับ ทำให้ลำดับกลายเป็น {1, 4, 5, 6, 5, 2, 1} ความยาว 7

สำหรับ query ที่สอง ค่าที่จะแทรกคือ 6 ซึ่งไม่สามารถแทรกได้ เพราะ 6 เป็นค่าสูงสุดอยู่แล้ว ดังนั้น 6 จะไม่ถูกแทรก

ลำดับสุดท้าย: {1, 4, 5, 6, 5, 2, 1} ความยาว 7

วิธีแก้ปัญหา

เราจะแบ่งลำดับ Bitonic ออกเป็น 2 เซต (Sets):

• เซตสำหรับส่วนที่เพิ่มขึ้น (incSet) จนถึงค่าสูงสุด
• เซตสำหรับส่วนที่ลดลง (decSet)

สำหรับแต่ละค่าที่จะแทรก จะมีกรณีดังนี้:

กรณี 1 (ค่ามากกว่าค่าสูงสุด) − เพิ่มค่าที่ปลายทางของ incSet และอัปเดตค่าสูงสุด

กรณี 2 − ถ้าค่าน้อยกว่าค่าสูงสุด ตรวจสอบใน incSet ก่อน หากยังไม่มีค่านั้น ให้แทรก ถ้ามีอยู่แล้ว ให้ค้นหาใน decSet และแทรกได้หากยังไม่มี

กรณี 3 (ค่าเท่ากับค่าสูงสุด หรือมีอยู่ในทั้ง incSet และ decSet) − ไม่แทรกค่านั้น

หลังจากแต่ละ query เราจะหาความยาวของลำดับ Bitonic โดยรวมความยาวของทั้งสองเซต:

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

หลังจากเสร็จสิ้นทุก queries ให้พิมพ์ลำดับ Bitonic โดยพิมพ์ 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 << "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 };
    calcBitonicSeqLength(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