蓝桥杯 17110抓娃娃

问题描述

小明拿了 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}.

运行限制

首先题目保证了 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;
}