バイナリ配列のクエリ操作を効率的に処理するC++コードの解説

n 個の要素を持つ配列 A と、q 個のクエリを含むリスト Q が与えられる問題を考えてみましょう。配列 A の各要素は、初期状態で 0 または 1 のいずれかです。各クエリ Query[i] はペア (x, k) で構成されており、それぞれ次のような意味を持ちます。

• x = 0(更新クエリ):A[k] の値を反転します。つまり 0 なら 1 に、1 なら 0 に切り替えます。
• x = 1(取得クエリ):現在の配列における「k 番目に大きい要素」を出力します。

たとえば、入力が A = [1, 1, 0, 1, 0]、Q = [[1, 2], [0, 1], [1, 2], [1, 0], [1, 4]] の場合、出力は 1, 1, 1, 0 となります。

解法の考え方

この問題を解く鍵となるのは、「配列の要素が 0 か 1 しかない」という制約です。配列を降順に並べると必ず [1, 1, …, 1, 0, 0, …, 0] という形になるため、k 番目に大きい要素が 1 になるのは「配列内の 1 の個数が k 以上である場合」だけです。したがって、クエリごとにソートや走査を行う必要はなく、1 の個数をカウント変数 m として管理するだけでよいことが分かります。

アルゴリズムの手順

1. 配列 A を一度走査し、非ゼロ(=1)の要素の個数を m としてカウントします。
2. 各クエリ (x, k) について、次の処理を行います。
   • x = 0 の場合:A[k] が非ゼロなら m を 1 減らし、ゼロなら m を 1 増やします。その後、A[k] を XOR 演算(^= 1)によって反転します。
   • x = 1 の場合:m >= k であれば 1 を出力し、そうでなければ 0 を出力します。

C++での実装例

それでは、実際のコードを見てみましょう。

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

void solve(vector<int> A, vector<vector<int>> Q){
   int n = A.size();
   int m = 0;
   // 初期状態の 1 の個数をカウント
   for (int i = 0; i < n; i++){
      if (A[i])
         m++;
   }
   for (int j = 0; j < Q.size(); j++){
      int x = Q[j][0];
      int k = Q[j][1];
      if (x == 0){
         // 更新クエリ:要素を反転し、カウントも同時に更新
         if (A[k])
            m--;
         else
            m++;
         A[k] ^= 1;
      }
      else{
         // 取得クエリ:k 番目に大きい要素を出力
         if (m >= k)
            cout << 1 << ", ";
         else
            cout << 0 << ", ";
      }
   }
}

int main(){
   vector<int> A = { 1, 1, 0, 1, 0 };
   vector<vector<int>> Q = { { 1, 2 }, { 0, 1 }, { 1, 2 }, { 1, 0 }, { 1, 4 } };
   solve(A, Q);
}

入力

{ 1, 1, 0, 1, 0 }, { { 1, 2 }, { 0, 1 }, { 1, 2 }, { 1, 0 }, { 1, 4 } }

出力

1, 1, 1, 0,

実行結果の流れ

初期状態では A = [1, 1, 0, 1, 0] なので、1 の個数 m は 3 です。各クエリは以下のように処理されます。

1. {1, 2}:m = 3 ≥ 2 なので 1 を出力。
2. {0, 1}:A[1] が 1 なので m を 3 → 2 に減らし、A[1] を 0 に反転。
3. {1, 2}:m = 2 ≥ 2 なので 1 を出力。
4. {1, 0}:m = 2 ≥ 0 なので 1 を出力。
5. {1, 4}:m = 2 < 4 なので 0 を出力。

計算量

初期化に O(n)、以降の各クエリ処理は O(1) で完了するため、全体の計算量は O(n + q) です。追加のメモリも O(1) で済むため、クエリの件数が非常に多い場合でも高速かつ効率的に動作します。「要素が 0 と 1 のみ」という制約を活かすことで、シンプルなカウント管理だけでクエリを捌けるのがこの手法の魅力です。