问题描述
小明拿了 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;
}
