问题描述
小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上,第 i 条线段的左端点在 li,右端点在 ri。小明用 m 个区间去框这些线段,第 i个区间的范围是 [Li, Ri]。如果一个线段有 至少一半 的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?
输入格式
输入共 n+m+1 行。
第一行为两个正整数 n, m。
后面 n 行,每行两个整数 li, ri。
后面 m 行,每行两个整数Li, Ri。
输出格式
输出共 m 行,每行一个整数。
样例输入
3 2
1 2
1 3
3 4
1 4
2 4
样例输出
3
2
评测用例规模与约定
对于 20%20% 的数据,保证 n,m≤。
对于 100%100% 的数据,保证 n,m≤,li<ri,0<li,ri,Li,Ri≤
,max{ri−li}≤min{Ri−Li}.
运行限制
语言 | 最大运行时间 | 最大运行内存 |
---|---|---|
C++ | 1s | 256M |
C | 1s | 256M |
Java | 3s | 256M |
Python3 | 3s | 256M |
PyPy3 | 3s | 256M |
Go | 3s | 256M |
JavaScript | 3s | 256M |
首先题目保证了 max{ri−li}≤min{Ri−Li},那么如果某个区间包含了某个线段,则该区间一定包含了这个线段的中点。
我们就可以在输入 li,ri 的时候,标记其中点 (mp[(l+r)/2]++)
,再做一遍前缀和,最后查询时 [Li,Ri] 这个区间的和就是答案。
注意:
有可能会出现中点的位置是个小数这种情况,所以我们不妨把所有坐标都 ×2 (不要忘记数组大小也要开两倍),以避免上述情况的发生。
#include<iostream>
using namespace std;const int N = 2e6+10;
int n, m; //n条线段 m个区间
int mp[N];int main()
{cin>>n>>m;int l, r;for(int i=1; i<=n; ++i){cin>>l>>r;mp[l+r]++; //记录每条线段中点的位置 }for(int i=1; i<N; ++i){mp[i] += mp[i-1];}for(int i=1; i<=m; ++i){cin>>l>>r;l *= 2;r *= 2;//一段区间包含了多少个中点就覆盖了多少条线段 cout<<mp[r] - mp[l-1]<<endl; //l-1:线段的中点恰好在 L 上 }return 0;
}