Truy vấn kiểm tra số có nằm trong N đoạn [L, R] C++

Cho N đoạn [L_i, R_i] và Q truy vấn. Mỗi truy vấn cho một số val. Kiểm tra val có thuộc ít nhất một đoạn hay không.

Ví dụ

Đoạn: {[2,4], [6,7], [9,12]}
Q1: val=1 → NO
Q2: val=7 → YES (trong [6,7])
Q3: val=10 → YES (trong [9,12])

Phương pháp 1: Duyệt tất cả đoạn O(N) mỗi truy vấn

Đơn giản, phù hợp N, Q nhỏ.

Phương pháp 2: Tiền xử lý + Binary Search O(log N)

Lưu tất cả đầu đoạn L_i và cuối đoạn R_i vào mảng points[], kèm loại (đầu/cuối). Sắp xếp points.

Dùng lower_bound tìm vị trí đầu tiên ≥ val.

• Nếu points[pos] == val → YES (val là đầu hoặc cuối đoạn).
• Ngược lại, xem points[pos] là đầu hay cuối đoạn:
  • Là cuối đoạn (R_i) → val nằm trong đoạn đó → YES.
  • Là đầu đoạn (L_i) → nằm ngoài mọi đoạn → NO.

Chương trình C++

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

bool queryInRanges(const vector>& ranges, int val) {
    // Tạo mảng sự kiện: {giá trị, loại} (loại: 0=đầu L, 1=cuối R)
    vector> events;
    for (auto [L, R] : ranges) {
        events.push_back({L, 0});
        events.push_back({R, 1});
    }
    sort(events.begin(), events.end());
    
    // Tìm vị trí đầu tiên >= val
    auto it = lower_bound(events.begin(), events.end(), make_pair(val, -1));
    
    if (it != events.end() && it->first == val) return true; // val là L hoặc R
    
    if (it == events.begin()) return false; // val < tất cả L
    if (it == events.end()) return false;   // val > tất cả R
    
    // it trỏ đến sự kiện đầu tiên > val
    // Kiểm tra sự kiện ngay trước đó
    auto prev = it - 1;
    return prev->second == 1; // Nếu trước đó là R → val nằm trong đoạn [L, R]
}

int main() {
    vector> ranges = {{2,4}, {6,7}, {9,12}};
    int Q = 3;
    int query[] = {1, 7, 10};
    for (int i = 0; i < Q; i++) {
        cout << "Query " << i+1 << ": val=" << query[i] 
             << " -> " << (queryInRanges(ranges, query[i]) ? "YES" : "NO") << endl;
    }
    return 0;
}

Kết quả

Query 1: val=1 -> NO
Query 2: val=7 -> YES
Query 3: val=10 -> YES

Độ phức tạp

Tiền xử lý: O(N log N). Mỗi truy vấn: O(log N). Rất hiệu quả cho Q, N lớn.