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

__zyq_666_kpzc__ · 2024-07-20 09:04:06 · 题解

题目传送门

思路分析

经过我 两分半 的思考得出：如果区间中包含了一条线段的至少一半，那么这条线段的中点一定在其中。毕竟，线段的一半及以上必定包含了中点。

我们可以在每次输入时将这条线段的中点记录下来，最后询问时再找区间中有多少个线段的中点即可。

注意：输出时暴力枚举来找线段的中点一定会超时，要开前缀和优化。

#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> sum;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        sum[(l+r)/2]++;
    }
    for(int i=1;i<=1000000;i++)
        sum[i]+=sum[i-1];
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<"\n";
    }
    return 0;
}