清華 OJ 範圍查詢問題：排序 + 二分查找 O((n+m)log n) 解法

問題描述

給定 n 個互不相同的點座標，回答 m 次查詢：每次詢問閉區間 [a, b] 內包含多少個點。
限制：n, m ≤ 5×10⁵，座標 ≤ 10⁷，時限 2s，記憶體 256MB。

解題思路

1. 將所有點座標讀入陣列並排序（qsort）。
2. 每次查詢轉化為：找第一個 ≥ a 的位置 lf，與第一個 > b 的位置 rt，答案 = rt - lf（若 a[rt] == b 則 +1）。
3. 使用迭代版二分查找避免遞歸棧溢出，並用 mid = left + ((right-left) >> 1) 防止溢出。

關鍵代碼片段

int find(int begin, int end, int ac) {
    int mid, left = begin, right = end;
    while (left <= right) {
        mid = left + ((right - left) >> 1);
        if (a[mid] >= ac) right = mid - 1;
        else left = mid + 1;
    }
    return left;
}

// 主循環
qsort(a, n, sizeof(int), compare);
for (i = 0; i < m; i++) {
    scanf("%d %d", &l, &r);
    if (l > r) swap(l, r);
    int rt = find(0, n-1, r);
    int lf = find(0, n-1, l);
    int ans = rt - lf;
    if (a[rt] == r) ans++;
    if (ans < 0) ans = 0;
    printf("%d\n", ans);
}

注意細節

• Tsinghua OJ 不支援 C++ algorithm 庫，需用 C 標準庫 qsort。
• 二分查找邊界調整：if (a[rt] == r) ans++; 處理右邊界命中情況。
• 迭代寫法比遞歸更高效且安全。

相關 OJ 推薦

清華 OJ 校外不可訪問，建議使用 POJ、ZOJ、HDU、UVA 等公開線上判題系統練習。