【C++】数値がN個の区間[L, R]のいずれかに含まれるかを判定するクエリ処理

この問題では、N個の区間 [L, R] と、それぞれ数値 val を含む Q 個のクエリが与えられます。求められるのは、各クエリで与えられた数値がN個の区間のうち少なくとも1つに含まれているかどうかを判定するプログラムをC++で作成することです。

問題の概要

N個の区間 [L, R] が与えられ、各区間は L から R までの整数をすべて含みます。たとえば区間 [3, 6] なら、3・4・5・6 の4つの整数を含みます。各クエリでは判定対象となる数値 val が渡され、val がいずれかの区間に含まれていれば true（存在する）、どの区間にも含まれていなければ false（存在しない）を返します。

入出力例

入力:
ranges[N] = {{2, 4}, {6, 7}, {9, 12}}
Q = 3
Query = {1, 7, 10}

出力:
Not Present
Present
Present

判定結果の解説

• クエリ1: 数値 1 は、どの区間にも含まれていません。
• クエリ2: 数値 7 は、区間 {6, 7} に含まれています。
• クエリ3: 数値 10 は、区間 {9, 12} に含まれています。

解法のアプローチ

クエリごとにすべての区間を線形に走査すると、区間数やクエリ数が増えた場合に非効率になります。そこで、ハッシュマップと二分探索（lower_bound）を組み合わせることで、高速な判定を実現します。手順は以下のとおりです。

1. すべての区間の始点 L と終点 R を1つの配列にまとめて格納し、昇順にソートします。
2. ハッシュマップを使って、各値が区間の始点（マーク値1）か終点（マーク値2）かを記録しておきます。
3. 各クエリでは、ソート済み配列に対して lower_bound により二分探索を行い、val 以上で最小の要素を取得します。
4. 取得した要素が val と一致すれば、val はある区間の端点として存在します。一致しない場合でも、その要素が区間の終点 R であれば、val はその区間の内部に含まれると判定できます。それ以外の場合は、val はどの区間にも属しません。

C++実装例

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
unordered_map<int, int> mpp;
void initialiseMap(int a[][2], int n){
    for (int i = 0; i < n; i++) {
        v.push_back(a[i][0]);
        mpp[a[i][0]] = 1;
        v.push_back(a[i][1]);
        mpp[a[i][1]] = 2;
    }
    sort(v.begin(), v.end());
}
bool isElementPresent(int val) {
    int ind = lower_bound(v.begin(), v.end(), val) - v.begin();
    if (v[ind] == val)
        return true;
    else {
        if (mpp[v[ind]] == 2)
            return true;
        else
            return false;
    }
}
int main(){
    int arr[][2] = {{2, 4}, {6,7}, {9, 12}};
    int n = 3;
    int Q = 3;
    int query[] = { 1, 7, 10 };
    initialiseMap(arr, n);
    for(int i = 0; i < Q; i++){
        cout<<"For Query "<<(i+1);
        if(isElementPresent(query[i]))
            cout<<": The given digit "<<query[i]<<" is present in one of the given ranges\n";
        else
            cout<<": The given digit "<<query[i]<<" is not present in any of the given ranges\n";
    }
    return 0;
}

出力結果

For Query 1: The given digit 1 is not present in any of the given ranges
For Query 2: The given digit 7 is present in one of the given ranges
For Query 3: The given digit 10 is present in one of the given ranges

計算量の目安

• 前処理（区間端点の格納とソート）: O(N log N)
• クエリ1回あたりの判定: O(log N)
• 全体の計算量: O((N + Q) log N)

このように二分探索を活用することで、区間数やクエリ数が大きくなっても各判定を対数時間で処理でき、非常に効率的な解法となります。なお、実運用では val が全端点より大きい場合など境界条件の扱いにも注意が必要です。