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

思路

1.其实题目保证了 $\max r_i-l_i\le \min R_i-L_i$，那么如果占了一半的话，那么肯定包含了中点，做一个前缀和就好了。

2.因为涉及了小数，给每个数字都乘以 $2$ 再继续操作。

代码（不能抄！！！）：

#include <bits/stdc++.h>  // 引入几乎所有STL库
#define int long long  // 定义'int'关键字为长整型（64位），便于处理大整数
using namespace std;  // 使用标准命名空间，避免std::

int n, m, arr[2000010], a, b;  // 声明全局变量，n和m是输入的整数，arr是长达2000010的数组，a和b用来临时存储读入的值

signed main() {  // 主函数，使用'signed'关键词限定main返回的是带符号的整数
    ios::sync_with_stdio(false);// 关闭C++和C的输入输出同步，加快cin和cout的速度
  while(1){}
    cin >> n >> m;  // 读入两个整数n和m
    for (int i = 1; i <= n; i++) {  // 从1循环到n
        cin >> a >> b;  // 读入每对a和b的值
        arr[(a + b)]++;  // 对数组的a+b索引处的值加一，统计出现的次数
    }
    for (int i = 1; i < 2000010; i++) arr[i] += arr[i - 1];  // 对数组进行前缀和处理，每个元素的值都加上它之前所有元素的和
    for (int i = 1; i <= m; i++) {  // 从1循环到m
        cin >> a >> b;  // 读入每对a和b的值
        a *= 2, b *= 2;  // a和b都乘以2，这有可能是为了避免小数或其他算法上的原因
        cout << arr[b] - arr[a - 1] << endl;  // 输出区间[a, b]的累加和，等于arr[b]减去arr[a - 1]
    }
    return 0;  // 返回0，正常退出程序
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23