P9426

nj_peak · 2023-10-26 22:03:13 · 题解

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

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

思路

前缀和加整体思想。

由题知，设这个区间 len，如果这个区间含有整个线段，那么一定含有这个线段的中点。所以我们标记中点的坐标，进行一个前缀和就可以了！！！

代码

#include<bits/stdc++.h>//万能头 
using namespace std;
int n,m;
int a[114514];
int x,y,xx,yy;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        a[x+y]++;       //标记中点 
    }
    for(int i=1;i<114514;i++){//前缀和 
        a[i]+=a[i-1];
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&xx,&yy);
        xx*=2;
        yy*=2;
        printf("%d\n",a[yy]-a[xx-1]);//输出 
    }
    return 0;
}