C++プログラムで解く配列の範囲クエリ：値と出現回数が一致する要素を数える方法

はじめに

今回は一風変わったアルゴリズムの問題を紹介します。N個の要素からなる配列が与えられ、次のような形式のクエリQを処理することが求められます。

Q(start, end) … start番目からend番目までの範囲内で、「ある数pがちょうどp回出現する」という条件を満たす要素の種類数を求める。

例えば、次の配列を考えてみましょう。

{1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8}

この配列に対するクエリの実行結果は以下のようになります。

• Q(1, 8) — インデックス1〜8の範囲では、「1」が1回、「3」が3回出現しています。したがって答えは2です。
• Q(0, 2) — インデックス0〜2の範囲では、「1」が1回だけ出現しています。したがって答えは1です。

アルゴリズム

この問題は、マップ（連想配列）を使って各要素の出現頻度を記録することで、シンプルに解くことができます。手順は以下の通りです。

query(s, e) の手順：
Begin
    範囲 [s, e] 内の各要素について、mapを使って出現頻度を記録する
    count := 0 で初期化
    map内の各キーと値のペア p について繰り返し：
        もし p.key = p.value（値と出現回数が一致）ならば
            count := count + 1
        繰り返し終了
    count を返す
End

C++による実装例

それでは、実際のコードを見てみましょう。std::mapを使用することで、要素の頻度管理とソート済みの走査を簡単に行えます。

#include <iostream>
#include <map>
using namespace std;

int query(int start, int end, int arr[]) {
    map<int, int> freq;
    // 範囲内の要素を取得し、出現頻度を記録
    for (int i = start; i <= end; i++)
        freq[arr[i]]++;

    int count = 0;
    for (auto x : freq)
        if (x.first == x.second) // 値と出現回数が一致したらカウント
            count++;
    return count;
}

int main() {
    int A[] = {1, 5, 2, 3, 1, 3, 5, 7, 3, 9, 8};
    int n = sizeof(A) / sizeof(A[0]);

    int queries[][2] = {
        { 0, 1 },
        { 1, 8 },
        { 0, 2 },
        { 1, 6 },
        { 3, 5 },
        { 7, 9 }
    };

    int query_count = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < query_count; i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        cout << "Answer for Query " << (i + 1)
             << " = " << query(start, end, A) << endl;
    }
}

実行結果

Answer for Query 1 = 1
Answer for Query 2 = 2
Answer for Query 3 = 1
Answer for Query 4 = 1
Answer for Query 5 = 1
Answer for Query 6 = 0

計算量について

この実装では、1回のクエリにつき最大O(N log N)の時間がかかります（範囲の走査にO(N)、マップへの挿入・走査にO(N log N)）。クエリ数をQとすると、全体の計算量はO(Q × N log N)となります。

クエリの数や配列のサイズが非常に大きい場合は、平方分割やモーズアルゴリズム（Mo's algorithm）などの高度なテクニックを用いることで、さらに効率化することも可能です。ただし、小規模な入力であれば、このシンプルなマップベースのアプローチで十分に実用的です。

まとめ

本記事では、「値とその出現回数が一致する要素」を範囲クエリで数える問題をC++で解きました。ポイントは以下の通りです。

• std::mapを使えば、要素ごとの出現頻度を簡単に管理できる
• キー（要素の値）と値（出現回数）を比較するだけで答えが求まる
• 大規模データには平方分割やMo's algorithmなどの最適化手法がある