C++で解く「接尾辞内の異なる整数の個数」クエリ問題：効率的な前計算アルゴリズム

この記事では、配列 arr[]（要素数 n の整数値）と、それぞれ整数 k を含む Q 個のクエリが与えられたとき、「接尾辞内に存在する異なる整数の個数」を効率的に求める C++ プログラムを紹介します。

問題の概要

各クエリに対して、インデックス k から n までの範囲、すなわち arr[k] から arr[n] までに含まれる一意な要素の数を求める必要があります。

※ 配列は 1 インデックス（1 起点）とします。

入出力例

入力

arr[] = {5, 1, 2, 1, 6, 5}, n = 6, Q = 3, query = {1, 3, 4}

出力

4 4 3

解説

クエリ 1: k = 1 の場合 → arr[1]〜arr[6] の範囲 {5, 1, 2, 1, 6, 5} の一意な要素は {5, 1, 2, 6} の 4 個
クエリ 2: k = 3 の場合 → arr[3]〜arr[6] の範囲 {2, 1, 6, 5} の一意な要素は 4 個
クエリ 3: k = 4 の場合 → arr[4]〜arr[6] の範囲 {1, 6, 5} の一意な要素は 3 個

シンプルな解法（ナイーブなアプローチ）

最も単純な方法は、各クエリごとにインデックス k から n まで順番に走査し、その範囲内の一意な要素を数えて返すことです。しかし、この方法ではクエリごとに O(n) の計算が必要となり、Q 個のクエリがある場合は全体で O(Q × n) の時間計算量となり、非効率です。

効率的な解法（前計算によるアプローチ）

より効率的な解法は、事前に計算されたデータ構造を利用することです。具体的には、インデックス (n-1) から 0 に向かって配列を逆順に走査しながら、unordered_set を使って重複する要素の追加を防ぎ、各位置における一意な要素の累積個数を補助配列に記録します。

この前計算により、各クエリには配列参照 1 回で答えられるため、全体の処理が大幅に高速化されます。

C++ 実装例

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

void solveQueries_DistInt(int n, int arr[], int Q, int queries[]) {
    unordered_set<int> uniqueInts;
    int distIntCount[n + 1];

    // 後ろから前へ走査し、各位置での一意な要素数を記録
    for (int i = n - 1; i >= 0; i--) {
        uniqueInts.insert(arr[i]);
        distIntCount[i + 1] = uniqueInts.size();
    }

    // 各クエリに即座に回答
    for (int i = 0; i < Q; i++)
        cout << "For Query " << (i + 1)
             << ": the number of distinct integers in Suffix is "
             << distIntCount[queries[i]] << endl;
}

int main() {
    int n = 6, Q = 3;
    int arr[n] = {5, 1, 2, 1, 6, 5};
    int queries[Q] = {1, 3, 4};

    solveQueries_DistInt(n, arr, Q, queries);
    return 0;
}

実行結果

For Query 1: the number of distinct integers in Suffix is 4
For Query 2: the number of distinct integers in Suffix is 4
For Query 3: the number of distinct integers in Suffix is 3

計算量のまとめ

このアプローチでは、前計算に O(n)、各クエリへの回答に O(1) かかるため、全体の時間計算量は O(n + Q) となります。クエリの数が多い場合でも高速に動作するのが大きな利点です。重複排除にはハッシュベースの unordered_set を使用しているため、平均的に挿入操作も高速です。