这是学完邓公的数据结构第二章向量(vector)之后的problem assignment，直接贴出题目的text：
描述 数轴上有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×10^5
对于每次查询的区间[a, b]，都有a ≤ b
各点的坐标互异
各点的坐标、查询区间的边界a、b，均为不超过10^7的非负整数
时间：2 sec
内存：256 MB
思路比较简单，大体上就是先对输入的整一组点进行排序，随后对其进行查找，找到给定区间的左端点和右端点，然后计算落在其中的元素的数目。
有几个细节需要注意一下，这道题的排序如果采用类似二路归并排序这种复杂度为O(nlogn) 的排序算法，最后几个测试案例是要TLE（超时）的，所以这边我采用的是计数排序（复杂度为O(n)，只要一趟循环就可以了），多开一个规模和输入规模相当的数组，用空间换时间；第二个要注意的是，如果这边采用的查找是邓俊辉的数据结构中采用的，即“返回一个不大于查找值的且在向量中秩最大的元素的位置”（白话就是待查找元素唯一时返回那个唯一的，待查找元素不唯一是返回最前面的，待查到元素找不到时返回小于它的最大元素）的话，要特判待查找元素小于数组最小元素的情形，因为这时候返回的秩是-1。
下面贴出完整版的AC代码：
#include <cstdio> #define COUNTING_SORT_ARRAY_CAPACITY 10000001 class Vector { public: Vector(int _size = 0) :m_size(_size) { m_elements = new int[m_size]; } ~Vector() { delete[] m_elements; } int size(void) {return m_size;} int& operator[] (int _rank) {return m_elements[_rank];} void sort(void) //通过牺牲空间换取时间，将向量元素的值映射到count数组的下标，下标对应的值记录出现次数 { if (! ordered()) { unsigned int* count_array = new unsigned int[COUNTING_SORT_ARRAY_CAPACITY]; for (int i = 0; i < COUNTING_SORT_ARRAY_CAPACITY; i++) //初始化置0 { count_array[i] = 0; } for (int i = 0; i < m_size; i++) //映射 { count_array[ m_elements[i] ]++; } int k = 0; for (int i = 0; i < COUNTING_SORT_ARRAY_CAPACITY; i++) //排序/ { while (count_array[i] != 0) { m_elements[k++]=i; count_array[i]--; } } delete[] count_array; } } int search(const int& _ele,int _low,int _high) const //采用二分查找的方式，返回不大于_ele的最大元素的下标 { while (_low < _high) { int mid = (_low + _high) / 2; if (_ele < m_elements[mid]) { _high = mid; } else { _low = mid + 1; } } return --_low; } protected: bool ordered(void) const //按升序排序的方法，判断当前向量中是否存在逆序对，元素需支持比较大小或者重载比较运算符 { bool ordered = true; for (int i = 0; i < m_size - 1; i++) { if (m_elements[i] > m_elements[i + 1]) { ordered = false; break; } } return ordered; } private: int* m_elements; int m_size; }; typedef struct ClosedInterval //存输入的待查找的闭区间 { int left_point, right_point; }ClosedInterval; int main() { //输入部分 int n, m; scanf("%d%d",&n,&m); //第一行输入两个整数：点的总数n，查询的次数m Vector v(n); for (int i = 0; i < v.size(); i++) { scanf("%d",&(v[i])); //第二行输入n个数，为各个点的坐标 } ClosedInterval* range = new ClosedInterval[m]; for (int i = 0; i < m; i++) { int a, b; scanf("%d%d",&a,&b); //以下m行，各包含两个整数：查询区间的左、右边界a和b range[i] = { a,b }; } //算法部分 v.sort(); //先对v排序 //二分查找区间端点的在数组中的位置，相减得到元素个数 for (int i = 0; i < m; i++) { int searched_left_point = range[i].left_point, searched_left_position = v.search(searched_left_point, 0, v.size()); if (searched_left_position == -1) //特判闭区间左端点小于数组第1位元素的情形 { int searched_right_point = range[i].right_point, searched_right_postion = v.search(searched_right_point, 0, v.size()); printf("%d\n", searched_right_postion + 1); } else { int searched_right_point = range[i].right_point, searched_right_postion = v.search(searched_right_point, searched_left_position, v.size()), count; v[searched_left_position] < range[i].left_point ? count = searched_right_postion - searched_left_position : count = searched_right_postion - searched_left_position + 1; printf("%d\n", count); } } delete[] range; return 0; }