题目描述 链接：https://ac.nowcoder.com/acm/contest/7157/H 来源：牛客网
Farmer John has just arranged his N haybales (1≤N≤100,000) at various points along the one-dimensional road running across his farm. To make sure they are spaced out appropriately, please help him answer Q queries (1≤Q≤100,000), each asking for the number of haybales within a specific interval along the road.
输入描述 The first line contains N and Q. The next line contains N distinct integers, each in the range 0…1,000,000,000, indicating that there is a haybale at each of those locations. Each of the next Q lines contains two integers A and B (0≤A≤B≤1,000,000,000) giving a query for the number of haybales between A and B, inclusive.
输出描述 You should write Q lines of output. For each query, output the number of haybales in its respective interval.
样例输入 4 6 3 2 7 5 2 3 2 4 2 5 2 7 4 6 8 10 样例输出 2 2 3 4 1 0
题目大意 在区间[0,1000000000]中有一些位置有haybales，求区间[A,B]内haybales的个数
思路 用sum[]数组保存前缀和，sum[i]表示区间[0,i]内haybales的个数，答案为sum[B]-sum[A-1]。但是数组下标无法达到1,000,000,000，我们注意到最多100,000个位置上有haybales，最多100,000个查询，所以实际使用到的下标最多300,000个，我们可以通过离散化处理下标问题。
AC代码
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 1e5+7; int mp[N*3], cnt, a[N], x[N], y[N], c[N*3], sum[N*3]; int n, Q; int main() { freopen("Counting Haybales.txt", "r", stdin); scanf("%d%d", &n, &Q); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); mp[++cnt] = a[i]; } for (int i = 1; i <= Q; i++) { scanf("%d%d", &x[i], &y[i]); mp[++cnt] = x[i]; mp[++cnt] = y[i]; } sort(mp+1,mp+cnt+1); cnt = unique(mp+1,mp+cnt+1)-mp; for (int i = 1; i <= n; i++) { int k = lower_bound(mp+1,mp+cnt+1,a[i])-mp; c[k]++; } for (int i = 1; i <= cnt; i++) { sum[i] = sum[i-1] + c[i]; } for (int i = 1; i <= Q; i++) { int xx = lower_bound(mp+1,mp+cnt+1,x[i])-mp; int yy = lower_bound(mp+1,mp+cnt+1,y[i])-mp; printf("%d\n", sum[yy]-sum[xx-1]); } return 0; }需要注意的点
排序后，使用unique()函数去重lower_bound()函数返回第一个大于等于的位置，upper_bound()函数返回第一个大于的位置，所以这里使用lower_bound()查找离散化后的下标