Counting Haybales
题目描述
Farmer John has just arranged his NN haybales (1≤N≤100,0001≤N≤100,000) at various points along t
he one-dimensional road running across his farm. To make sure they are spaced out appropriately, ple
ase help him answer QQ queries (1≤Q≤100,0001≤Q≤100,000), each asking for the number of haybales
within a specific interval along the road.
给出N(1≤N≤100,000)个数,和 Q(1≤Q≤100,000)个询问。每个询问包含两个整数A,B(0≤A≤B≤1,000,00
0,000)。对于每个询问,给出数值在A到B间的数有多少个(包含A与B)。
输入格式
The first line contains N and Q.The next line contains N distinct integers, each in the range 0…1,0
00,000,000 indicating that there is a haybale at each of those locations.Each of the next Q lines co
ntains two integers AA and BB (0≤A≤B≤1,000,000,000) giving a query for the number of haybales bet
ween A and B, inclusive.
输出格式
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
提示
Silver 鸣谢winmt提供译文
信息
- 难度
- 9
- 分类
- (无)
- 标签
- 递交数
- 2
- 已通过
- 1
- 通过率
- 50%
- 上传者