Truy vấn chèn phần tử vào dãy Bitonic trong C++

Trong bài toán này, ta được cho một dãy Bitonic và Q truy vấn. Mỗi truy vấn chứa một số nguyên x. Nhiệm vụ là in ra độ dài của dãy Bitonic sau khi chèn số nguyên đó sau mỗi truy vấn. Cuối cùng in ra dãy Bitonic hoàn chỉnh.

Mô tả bài toán

Cho một dãy Bitonic. Có Q truy vấn, mỗi truy vấn chứa một số nguyên cần thêm vào dãy. Ta sẽ thêm phần tử từ mỗi truy vấn vào dãy và trả về độ dài của dãy Bitonic. Sau khi hoàn tất tất cả truy vấn, in ra dãy Bitonic.

Dãy Bitonic là dãy đặc biệt mà giá trị các phần tử tăng dần đến một điểm (gọi là đỉnh Bitonic), sau đó giảm dần.

Ví dụ: 1, 5, 6, 8, 9, 7, 5, 2

Ví dụ minh họa

Đầu vào

bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6}

Đầu ra

7 7
{1, 4, 5, 6, 5, 2, 1 }

Giải thích

Truy vấn 1: Giá trị 5 được chèn vào phần tăng của dãy, tạo thành {1, 4, 5, 6, 5, 2, 1}, độ dài 7.

Truy vấn 2: Giá trị 6 không thể chèn vì 6 là giá trị lớn nhất (đỉnh). Do đó 6 không được chèn thêm.

Dãy cuối cùng: {1, 4, 5, 6, 5, 2, 1}, độ dài 7.

Cách giải: Tách dãy Bitonic thành hai tập hợp (set): một cho phần tăng dần đến giá trị lớn nhất, một cho phần giảm dần.

Với mỗi phần tử cần chèn, có các trường hợp sau:

• Trường hợp 1 (phần tử lớn hơn max): Thêm vào cuối phần tăng, cập nhật max mới.
• Trường hợp 2 (phần tử nhỏ hơn max): Kiểm tra trong tập tăng trước, nếu chưa có thì chèn vào. Ngược lại, kiểm tra trong tập giảm và chèn nếu có thể.
• Trường hợp 3 (phần tử bằng max hoặc đã tồn tại ở cả hai tập): Không chèn phần tử này.

Sau mỗi truy vấn, độ dài dãy Bitonic = kích thước tập tăng + kích thước tập giảm.

Sau tất cả truy vấn, in dãy Bitonic bằng cách in tập tăng theo thứ tự tăng dần, rồi tập giảm theo thứ tự giảm dần.

Chương trình minh họa:

Ví dụ

#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: ";
    for (auto it = incSet.begin(); it != incSet.end(); it++)
        cout << (*it) << " ";
    for (auto 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;
}

Đầu ra

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