C++で部分配列内の異なる要素の数をクエリ処理で求める方法

この記事では、サイズ n の配列 arr[] と、範囲を指定する2つの値 l・r からなる Q 個のクエリが与えられたとき、C++ を使って各部分配列（サブ配列）に含まれる異なる要素（ユニークな要素）の数を効率的に求めるプログラムの作成方法を解説します。

問題の概要

各クエリに対して、arr[l] から arr[r] までの部分配列に含まれる相異なる整数の総数を求める必要があります。同じ値が複数回現れても、それは1つとしてカウントします。

具体例で理解しよう

入力

arr[] = {5, 6, 1, 6, 5, 2, 1}
Q = 2
{{1, 4}, {0, 6}}

出力

3
4

説明

クエリ1の場合：
l = 1、r = 4 なので、subarray[1...4] = {6, 1, 6, 5} となります。重複を除いた異なる要素は {6, 1, 5} の 3つです。

クエリ2の場合：
l = 0、r = 6 なので、subarray[0...6] = {5, 6, 1, 6, 5, 2, 1} となります。重複を除いた異なる要素は {5, 6, 1, 2} の 4つです。

解決アプローチ：set（集合）を活用する

この問題を解く最もシンプルな方法は、STL の set データ構造を利用することです。set には以下のような特徴があります。

• 同じ値の要素は自動的に排除される（重複不可）
• 要素は常にソートされた状態で保持される

そのため、クエリで指定された範囲 [l, r] のすべての要素を set に挿入すれば、重複した要素は自動的に破棄され、異なる要素だけが格納されます。最終的な set のサイズ（size()）が、そのまま部分配列内の異なる要素の数になります。

実装プログラム

以下は、上記のアプローチを実装した C++ プログラムの完全なコードです。

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

int solveQuery(int arr[], int l, int r) {

    set<int> distElements;
    for (int i = (r); i >= (l); i--)
    distElements.insert(arr[i]);
    return distElements.size();
}

int main() {

    int arr[] = {5, 6, 1, 6, 5, 2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int Q = 2;
    int query[Q][2] = {{1, 4}, {0,6}};
    for(int i = 0; i < Q; i++)
    cout<<"For Query "<<(i+1)<<": The number of distinct elements in subarray is "<<solveQuery(arr, query[i][0], query[i][1])<<"\n";
    return 0;
}

実行結果

For Query 1: The number of distinct elements in subarray is 3
For Query 2: The number of distinct elements in subarray is 4

計算量の考察

この手法では、1つのクエリにつき範囲内の最大 (r − l + 1) 個の要素を set に挿入します。set への挿入は O(log n) の計算量を要するため、全体の時間計算量は O(Q × n × log n) 程度となります。クエリ数や配列サイズが大きい場合は、Mo's Algorithm（モズのアルゴリズム）やセグメント木など、より高度なオフライン処理手法を検討すると大幅な高速化が期待できます。

まとめ

C++ の set コンテナを使えば、部分配列内の異なる要素数を数えるクエリを簡潔かつ直感的に実装できます。まずはこのシンプルな手法をマスターし、必要に応じてより効率的なアルゴリズムへ発展させていくのがおすすめです。