Chương trình C++ thực hiện các truy vấn trên dãy số (thêm, in đầu, sắp xếp)

Mô tả bài toán

Dãy rỗng ban đầu, n truy vấn:

• Loại 1 x: thêm x vào cuối.
• Loại 2: in phần tử đầu và xóa nó.
• Loại 3: sắp xếp dãy tăng dần.

Ví dụ

n=9, queries={{1,5},{1,4},{1,3},{1,2},{1,1},{2,0},{3,0},{2,0},{3,0}}. Đầu ra: 5 1.

Thuật toán (Hai cấu trúc dữ liệu)

1. Hàng đợi q lưu phần tử chưa sắp xếp (thêm vào đuôi).
2. Hàng đợi ưu tiên priq (max-heap lưu giá trị âm) lưu phần tử đã sắp xếp.
3. Truy vấn 1: push vào .
4. Truy vấn 2: nếu rỗng → lấy từ ; ngược lại lấy từ .
5. Truy vấn 3: chuyển toàn bộ vào (lưu giá trị âm để max-heap thành min-heap).

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

void solve(int n, vector<pair<int,int>> queries){
    priority_queue<int> priq; // max-heap of -value
    queue<int> q;
    for(int i=0;i