范围统计问题

范围统计问题（参考刘汝佳《算法竞赛入门经典》P146）

问题描述：
　　给出 n 个整数和 m 次询问，对于每次询问 (a, b), 输出闭区间 [a, b] 内的整数的个数
分析：
　　预处理：
　　　　把数据存在数组里并从小到大排序
　　问题一：
　　　　大于等于 a 的第一个元素的下标 L 是什么？它等于 a 的lower_bound 值。
　　如果所有元素都小于a，则 L = n，相当于把不存在的元素看做无穷大。
　　问题二：
　　　　小于等于b 的最后一个元素的 "下一个下标" R 是什么？它等于 b 的upper_bound值，
　　如果所有的元素都大于 b ，则相当于 R = 0，相当于想象A[0] 前边还有一个A[-1]等于
　　负无穷大，则这个A[-1]的"下一个位置"就是 0 。
　　这样问题的答案就是区间[L, R] 的长度，即 R-L。顺便说一句，STL中已经包含了lower_bound
　　和upper_bound，可以直接使用。

代码实现：

 1 #include <iostream>
 2 #include <algorithm>      // STL算法头文件，包含sort, lower_bound 和 upper_bound等
 3 
 4 using namespace std;
 5 
 6 int v[1000];
 7 
 8 int main()
 9 {
10     int n, m, a, b;
11     cin >> n >> m;
12     for(int i = 0; i < n; ++i)
13         cin >> v[i];
14     sort(v, v+n);
15     for(int i = 0; i < m; ++i)
16     {
17         cin >> a >> b;    //   询问 [a, b]  内的整数的个数
18         cout << upper_bound(v, v+n, b) - lower_bound(v, v+n, a) << endl;
19         // 注意当a > b 时候返回的结果为负数
20     }
21 }

两个函数也可以自己定义如下：

　　二分查找求下界的函数：

　　　　当 v 存在时返回它出现的第一个位置。如果不存在，返回这样一个下标i：在此处插入 v后数列仍然有序。

 1 int low_bound(int *A, int x, int y, int v)
 2 {
 3     int m;
 4     while(x < y)
 5     {
 6         m = x + (y-x)/2;
 7         if(A[m] >= v)
 8             y = m;
 9         else
10             x = m+1;
11     }
12     return x;
13 }

二分查找求上界的函数：
　　当 v 存在时返回它最后出现的下一个位置。如果不存在，返回这样一个下标i ：在此处插入 v后数列仍然有序：

 1 int upper_bound(int *A, int x, int y, int v)
 2 {
 3     int m;
 4     while(x < y)
 5     {
 6         m = x + (y-x)/2;
 7         if(A[m] <= v)
 8             x = m+1;
 9         else
10             y = m;
11     }
12     return x;
13 }