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

· · 题解

抓娃娃（蓝桥杯 2023 国赛 17110）

赛上写这道题时很快，看到区间和就想到前缀和，但对于抓取的判定，有点模糊，想是区间只刚好覆盖到中点，要做个特判。

赛后：\ 赛时的问题在数据范围已经被解决，即题目保证 \max \{r_i - l_i\} \le \min \{R_i - L_i\}，翻译一下就是保证每个区间都可以完整地覆盖一条线段。

因为对于线段而言，只要至少一半的长度被包含则就会被某个区间框柱，那么，也就是说，只要包含其中一个端点和这个线段的中点即可。

因此，将所有线段按照中点位置从小到大排序，然后，对于每一个查询的区间，用前缀和计算该区间包含的线段数量。

当然，除了用前缀和的方法，也可以使用二分来进行计算。

Code：

/*
忽略每条线段，取而代之的是他们的中点
前缀和(线段树doge)
TODO
*/
#include <bits/stdc++.h>
using namespace std;
int n, m;
int sum[2000010];
int main() {
    //  freopen("catch.in","r",stdin);
    //  freopen("catch.out","w",stdout);

    cin >> n >> m;
    int l, r;
    for (int i = 1; i <= n; i++) {
        cin >> l >> r;
        int mid = l + r;
        //记录线段中点坐标(用于判断是否在区间内)
        sum[mid]++;
    }
    for (int i = 1; i <= 1000010; i++) {
        sum[i] += sum[i - 1];
    }
    int L, R;
    for (int i = 1; i <= m; i++) {
        cin >> L >> R;
        L *= 2, R *= 2;
        cout << sum[R] - sum[L - 1] << endl;
    }
    return 0;
}