【問題描述】
數軸上有n個點，對於任一閉區間 [a, b]，試計算落在其內的點數。
【輸入】
第一行包括兩個整數：點的總數n，查詢的次數m。
第二行包含n個數，為各個點的坐標。
以下m行，各包含兩個整數：查詢區間的左、右邊界a和b。
【輸出】
對每次查詢，輸出落在閉區間[a, b]內點的個數。
【輸入樣例】
5 2
1 3 7 9 11
4 6
7 12
【輸出樣例】
0
3
【限制】
0 ≤ n, m ≤ 5×105
對於次查詢的區間[a, b]，都有a ≤ b
各點的坐標互異
各點的坐標、查詢區間的邊界a、b，均為不超過10^7的非負整數
時間：2s，內存：256MB
【solution】先不廢話，先貼源代碼：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 #define L 500005
5
6 int a[L];
7
8 int compare(const void *a, const void *b)
9 {
10 int *pa = (int*)a;
11 int *pb = (int*)b;
12 return (*pa) - (*pb);
13 }
14
15 void swap(int &a, int &b)
16 {
17 int temp;
18 temp = a;
19 a = b;
20 b = temp;
21 }
22
23 int find(int begin, int end, int ac)
24 {
25 int mid, left = begin, right = end;
26 while (left <= right)
27 {
28 mid = left + ((right - left) >> 1);
29 if (a[mid] >= ac) right = mid - 1;
30 else left = mid + 1;
31 }
32 return left;
33 }
34
35
36 int main()
37 {
38 int n, m, i;
39 scanf("%d %d\n", &n, &m);
40
41 for (i = 0; i < n; i++)
42 {
43 scanf("%d", &a[i]);
44 }
45
46 //refer to http://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html
47 qsort(a, n, sizeof(int), compare);
48
49 for (i = 0; i < m; i++)
50 {
51 int l, r, ans, lf, rt;
52 scanf("%d %d", &l, &r);
53
54 //make sure l <= r
55 if (l > r)
56 {
57 swap(l, r);
58 }
59
60 rt = find(0, n - 1, r);
61 lf = find(0, n - 1, l);
62 ans = rt - lf;
63 if (a[rt] == r) ans++;
64 if (ans < 0) ans = 0;
65
66 printf("%d\n", ans);
67 }
68 }
第一感覺都是這道題以前學的時候肯定做過，很簡單，看到這個數據規模基本也就確定得用二分查找了。（反正看網上想先維護好線性數組再O(1)的查找是沒混過去的）
實際上，二分查找並沒有看起來那麼簡單，尤其是具體寫起來的時候，有很多細節與臨界點的處理都得根據實際情況仔細斟酌。
結合上述源代碼，有幾點值得注意的地方：
1）qsort的用法，參考了：http://www.cnblogs.com/CCBB/archive/2010/01/15/1648827.html。 Tsinghua OJ 不支持 algorithm 庫。
2）倒數第三行代碼（if (a[rt] == r) ans++;）實際上就是二分查找結合具體情況對答案的調整。不妨分上界和下界等於或者不等於a數組中的值分情況討論，即可明白這一行的涵義。這也跟二分查找幾個細節的處理相統一。
3）二分查找函數中這一行：mid = left + ((right - left) >> 1);。一方面，位運算提高運算效率；另一方面，不直接用 (left + right) >> 1 防止計算過程中數字越界，進而導致數組下標越界。
4）二分查找不要用遞歸形式。一是提高效率；二是防止堆棧溢出。
不能，去ZOJ，或者POJ都很出名的
清華沒有你說的Online Judge.北大的OJ不錯，網址是poj.org/
浙大： acm.zju.edu.cn/onlinejudge/
USACO: ace.delos.com/usacogate
Uva: uva.onlinejudge.org/
杭電 acm.hdu.edu.cn/
廈大： acm.xmu.edu.cn/JudgeOnline/
西電： xdoj.maybe.im/JudgeOnline/
希望對你有幫助。
