自动搬运

查看原文

来自洛谷，原作者为

	EchoHua0402 sdsz准初三||♀||Always be humble. || Believe the power of belief.||RP++

搬运于2025-08-24 22:48:16，当前版本为作者最后更新于2023-07-06 16:28:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9426 [蓝桥杯 2023 国 B] 抓娃娃 题解

思路

这道题的整体思路以及需要用到的算法：一点思维+前缀和/差分。

首先题目保证了 $\max \{r_i-l_i\} \leq \min\{R_i-L_i\}$，那么如果某个区间包含了某个线段，则该区间一定包含了这个线段的中点。

这样一来，我们就可以在输入 $l_i,r_i$ 的时候，标记其中点 (mp[(l+r)/2]++)，再做一遍前缀和（方便过会儿使用），最后查询时 $[L_i,R_i]$ 这个区间的和就是答案。

注意：

我就是因为这个被卡了。

有可能会出现中点的位置是个小数这种情况，所以我们不妨把所有坐标都 $\times 2$ （不要忘记数组大小也要开两倍），以避免上述情况的发生。

附上完整 AC 代码~

#include <bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int 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;
	}
	return 0;
}