## Question

Tsinghua Online Judge 范围查询(Range)

## Solution

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;
}