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

· · 题解

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;
}