C++でシーケンスに対する3種類のクエリ操作を効率的に処理する方法

問題の概要

空のシーケンスと、処理すべき n 個のクエリが与えられます。クエリは配列 queries に {query, data} の形式で格納されており、次の3種類があります。

• query = 1: 指定されたデータをシーケンスの末尾に追加する。
• query = 2: シーケンスの先頭にある要素を出力し、その後その要素を削除する。
• query = 3: シーケンスを昇順にソートする。

なお、クエリタイプ2と3では常に data = 0 が渡されることに注意してください。

入力例

n = 9、queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}} の場合、出力は 5 と 1 になります。

各クエリ後のシーケンスの状態

• 1: {5}
• 2: {5, 4}
• 3: {5, 4, 3}
• 4: {5, 4, 3, 2}
• 5: {5, 4, 3, 2, 1}
• 6: {4, 3, 2, 1} → 5 を出力
• 7: {1, 2, 3, 4}
• 8: {2, 3, 4} → 1 を出力
• 9: {2, 3, 4}

解決のアプローチ

この問題は、通常のキュー（queue）と優先度付きキュー（priority_queue）を組み合わせることで効率的に解けます。ポイントは、ソート済みの要素を優先度付きキュー側に保持し、未ソートの要素を通常のキューに保持するという考え方です。優先度付きキューはデフォルトで最大値を取り出すため、負の値を格納することで最小値（昇順の先頭）を取得できるようにします。

アルゴリズムの手順

priority_queue<int> priq   // ソート済み要素を保持（負の値で格納）
queue<int> q               // 未ソート要素を保持
i := 0 から i < n まで i を1ずつ増やしながら繰り返す:
    operation := queries[i] の1つ目の値
    operation が 1 の場合:
        x := queries[i] の2つ目の値
        x を q に挿入する
    operation が 2 の場合:
        priq が空ならば:
            q の先頭要素を出力し、削除する
        そうでなければ:
            -(priq の先頭要素) を出力し、priq の先頭を削除する
    operation が 3 の場合:
        q が空になるまで繰り返す:
            -(q の先頭要素) を priq に挿入する
            q から要素を削除する

C++による実装例

以下の実装を見ると、動作をより深く理解できます。

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

void solve(int n, vector<pair<int, int>> queries){
   priority_queue<int> priq;
   queue<int> q;
   for(int i = 0; i < n; i++) {
      int operation = queries[i].first;
      if(operation == 1) {
         int x;
         x = queries[i].second;
         q.push(x);
      } else if(operation == 2) {
         if(priq.empty()) {
            cout << q.front() << endl;
            q.pop();
         } else {
            cout << -priq.top() << endl;
            priq.pop();
         }
      } else if(operation == 3) {
         while(!q.empty()) {
            priq.push(-q.front());
            q.pop();
         }
      }
   }
}
int main() {
   int n = 9; vector<pair<int, int>> queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0},  {3, 0}, {2, 0}, {3, 0}};
   solve(n, queries);
   return 0;
}

入力

9, {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}

出力

5
1

計算量について

このアプローチでは、要素の追加は O(1)、ソート操作はキュー内の全要素を優先度付きキューへ移すため全体で O(k log k)（k は移動対象の要素数）、先頭要素の出力と削除は O(log k) となります。毎回 std::sort で全要素を並べ替える素朴な手法よりも効率的であり、特にソートと取得が交互に行われるケースで優れたパフォーマンスを発揮します。