Question

Tsinghua Online Judge 范围查询(Range)

Solution

如果brute force硬算的话，相当于每一个组range都需要跑一次循环来看点在不在range中，复杂度为$O(nm)$ (n个point，m个range). 如果优化的话很容易能想到用binary search，具体思路如下：

  1. sort所有的points $O(nlog n)$
  2. 对每一个新range，在points里面binary search range的开头和结尾，相减得到此range里points的个数 $O(log n)$
  3. done

Time Complexity

$$ O(nlog n) + m\times O(log n) = O(nlog n + mlogn) $$

#include <stdio.h>
#include <stdlib.h>

// Function to compare integers for qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// Function to perform binary search
int binary_search(int *arr, int n, int x) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    int points[n];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &points[i]);
    }
    
    // Sort the points
    qsort(points, n, sizeof(int), compare);
    
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        
        // Use binary search to find the count of points lying inside [a, b]
        int count = binary_search(points, n, b) - binary_search(points, n, a - 1);
        printf("%d\n", count);
    }
    
    return 0;
}