C++でL番目とR番目に小さい要素の絶対差を求めるクエリ処理プログラム

この問題では、サイズ n の配列 arr[] と、それぞれ2つの値 L と R からなる Q 個のクエリが与えられます。各クエリに対して、L番目に小さい数値と R番目に小さい数値の絶対差を返すプログラムを作成するのが課題です。

問題の概要

各クエリを解くためには、L番目に小さい要素と R番目に小さい要素が元の配列のどのインデックスに位置するかを特定し、そのインデックス同士の差（絶対値）を求める必要があります。

例を使って問題を理解しましょう。

入力

arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}}

出力

1 2

説明

{2, 4} の場合：2番目に小さい要素は「2」で、そのインデックスは 4
4番目に小さい要素は「5」で、そのインデックスは 3
差 = |4 - 3| = 1

{1, 5} の場合：最小の要素は「1」で、そのインデックスは 2
5番目に小さい要素は「8」で、そのインデックスは 0
差 = |2 - 0| = 2

解法アプローチ①：pair を使う方法

この問題を解くには、配列の各要素の「値」と「インデックス」をペアとして格納し、それを昇順にソートします。ソート後、i番目の要素が i+1 番目に小さい値となるため、クエリごとに L-1 番目と R-1 番目のペアを参照すれば、目的のインデックスを O(1) で取得できます。あとは両インデックスの絶対差を出力するだけです。

この解法の動作を示すプログラム：

例

#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
    pair<int, int> arrayIndex[n];
    for (int i = 0; i < n; i++) {
        arrayIndex[i].first = arr[i];
        arrayIndex[i].second = i;
    }  
    sort(arrayIndex, arrayIndex + n);
    for (int i = 0; i < Q; i++){
        int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
        cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
    }
}
int main() {
    int arr[] = { 8, 4, 1, 5, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

出力

For Query 1: Difference is 1
For Query 2: Difference is 2

解法アプローチ②：pair を使わない方法

pair データ構造を使用せずに同じ結果を得ることも可能です。この方法では、まず元の配列をコピーして昇順にソートした配列（minArray）を作成します。これにより、L番目および R番目に小さい値をすぐに取り出せます。次に、その値が元の配列のどこにあるかを線形探索で調べ、インデックスの絶対差を計算します。

この解法の動作を示すプログラム：

例

#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
    for(int i = 0; i < n; i++)
        if(arr[i] == ele)
            return i;
    return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
    int Lele = minArray[L-1];
    int Rele = minArray[R-1];
    int index1 = searchEle(arr, Lele, n);
    int index2 = searchEle(arr, Rele, n);
    return abs(index1 - index2);
}
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
    int minArray[n];
    for (int i = 0; i < n; i++)
        minArray[i] = arr[i];
    sort(minArray, minArray + n);
    for(int i = 0; i < Q; i++){
        cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n, queries[i][0], queries[i][1])<<endl;
    }
}
int main() {
    int arr[] = { 8, 4, 1, 5, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
    solveAllQueries(arr, n, Q, queries);
    return 0;
}

出力

For Query 1: Difference is 1
For Query 2: Difference is 2

計算量の比較

解法①（pair 使用）では、ソートに O(n log n)、各クエリへの応答は O(1) となり、全体の計算量は O(n log n + Q) です。一方、解法②（線形探索）では、各クエリごとに元の配列を探索するため O(n) かかり、全体で O(n log n + Q×n) となります。クエリ数が多い場合は、解法①のように前処理でインデックスを管理しておく方が効率的です。なお、解法②は重複した値が配列に含まれる場合、最初に見つかったインデックスを返す点にも注意が必要です。