Points in Segments(区间中的点)

2024-01-10 17:38

文章标签 区间 points segments

本文主要是介绍Points in Segments(区间中的点)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接

Given n points (1 dimensional) and q segments, you have to find the number of points that lie in each of the segments. A point pi will lie in a segment A B if A ≤ pi ≤ B.For example if the points are 1, 4, 6, 8, 10. And the segment is 0 to 5. Then there are 2 points that lie in the segment.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.Each case starts with a line containing two integers n (1 ≤ n ≤ 10 ^ 5) and q (1 ≤ q ≤ 50000). The next line contains n space separated integers denoting the points in ascending order. All the integers are distinct and each of them range in [0, 10 ^ 8].Each of the next q lines contains two integers Ak Bk (0 ≤ Ak ≤ Bk ≤ 108) denoting a segment.

Output

For each case, print the case number in a single line. Then for each segment, print the number of points that lie in that segment.

Sample Input

1
5 3
1 4 6 8 10
0 5
6 10
7 100000

Sample Output

Case 1:
2
3
2

Note

Dataset is huge, use faster I/O methods.

单词

Segment 部份，区间
dimensional 尺寸
ascending order 升序
space separated 空格分隔的

原文翻译

给定n个点（一维）和q个区间，您必须找到每个区间中的点数。如果A ≤ pi ≤ B，则点pi将位于区间A B中。例如，如果点是1、4、6、8、10，并且区间是0到5。则区间中有2个点。
输入以整数T（≤5）开头，表示测试用例的数量。
每种测试用例的第一行包含两个整数n（1 ≤ n ≤ 10 ^ 5）和q（1 ≤ q ≤ 50000）。下一行包含n个以空格分隔的整数，这些整数按升序表示点。所有整数都是不同的，并且每个整数的范围都在[0，10 ^ 8]。
接下来的q行，每行包含两个整数Ak Bk（0 ≤ Ak ≤ Bk ≤ 10 ^ 8）表示区间。
对于每种情况，请在一行中打印样例编号。然后，对于每个区间，打印该区间中的点数。

知识点

lower_bound： 返回数列中第一个大于或者等于所查询数的位置，没有大于等于所查询数返回数列长度
upper_bound： 返回数列中第一个大于所查询数的位置，没有大于所查询的数返回数列长度

样例分析

1
5 3
1 4 6 8 10
0 5
6 10
7 100000

对于第一组区间0 5

upper_bound(a,a + n,5)会返回第一个大于5的位置 — 2
lower_bound(a,a + n,0)会返回第一个大于等于0的位置—0
upper_bound(a,a + n,5) - lower_bound(a,a + n,0) = 2；
对于第二组区间6 10
upper_bound(a,a + n,10)会返回第一个大于10的位置 — 5(数列长度)
lower_bound(a,a + n,6)会返回第一个大于等于6的位置—2
upper_bound(a,a + n,10) - lower_bound(a,a + n,6) = 3；
对于第三组区间7 100000
upper_bound(a,a + n,100000)会返回第一个大于100000的位置 — 5(数列长度)
lower_bound(a,a + n,7)会返回第一个大于等于7的位置—3
upper_bound(a,a + n,100000) - lower_bound(a,a + n,7) = 2；

故若区间为[x,y]，输出的答案为upper_bound(a,a + n,y) - lower_bound(a,a + n,x)；

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5 + 10;
int a[N];
int n,q;//n、q分别表示数组中的元素个数和区间个数
int x,y;//表示区间int main()
{int t;scanf("%d",&t);//多组测试数据for (int k = 1;k <= t;k++){printf("Case %d:\n",k);scanf("%d%d",&n,&q);for (int i = 0;i < n;i++) scanf("%d",&a[i]);//读入n个数while (q--)//q组区间{scanf("%d%d",&x,&y);int ans1 = int(upper_bound(a,a + n,y) - a);int ans2 = int(lower_bound(a,a + n,x) - a);printf("%d\n",ans1 - ans2);}}return 0;
}