题目描述

难度分:$1400$

输入$n$，$k(1 \leq k \leq n \leq 2 \times 10^5)$，$q(1 \leq q \leq 2 \times 10^5)$。

然后输入$n$个$recipe$，每个$recipe$输入两个数$L$，$R(1 \leq L \leq R \leq 2 \times 10^5)$，表示冲一杯咖啡的推荐温度范围为$[L,R]$。

定义一个整数温度$t$是可接受的，如果$t$包含在至少$k$个$recipe$的推荐温度范围内。

然后输入$q$个询问，每个询问输入两个数$a$，$b(1 \leq a \leq b \leq 2 \times 10^5)$，输出$[a,b]$内有多少个温度是可接受的，每行一个答案。

输入样例$1$

3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100

输出样例$1$

3
3
0
4

输入样例$2$

2 1 1
1 1
200000 200000
90 100

输出样例$2$

0

算法

差分数组+二分查找

构建一个差分数组$delta$，在读入每个$recipe$的推荐温度区间$[L,R]$时，在$delta[L]$上加一，在$delta[R+1]$上减一，就相当于整个区间$[L,R]$上都是当前$recipe$所推荐的温度。

接下来遍历所有温度$t \in [1,2 \times 10^5]$，计算$delta$的前缀和，加入遍历到$t$温度时前缀和大于等于$k$，说明这个温度有至少$k$个$recipe$推荐，是一个可接受的温度，将其放入到数组$cands$中。

最后在读入$q$个询问时，就只需要二分查找确定$cands$中在$[a,b]$区间中的元素有多少个就可以了。

复杂度分析

时间复杂度

构建差分数组$delta$的时间复杂度为$O(n)$。获得$cands$数组需要遍历一遍$delta$数组，时间复杂度也是$O(n)$。$q$次询问每次都需要在$cands$数组中进行两次二分查找，时间复杂度是$O(log_2n)$的，因此整体时间复杂度为$O(qlog_2n)$。综上，整个算法的时间复杂度为$O(n+qlog_2n)$。

空间复杂度

空间瓶颈在于差分数组$delta$和可接受温度的数组$cands$，两者的规模都是$O(n)$的，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
const int N = 200010;
int n, k, q, l, r, a, b, delta[N];

int main() {
    scanf("%d%d%d", &n, &k, &q);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &l, &r);
        delta[l]++;
        delta[r + 1]--;
    }
    vector<int> cands;
    int presum = 0;
    for(int i = 1; i <= N - 10; i++) {
        presum += delta[i];
        if(presum >= k) cands.push_back(i);
    }
    for(int i = 1; i <= q; i++) {
        scanf("%d%d", &a, &b);
        int lb = lower_bound(cands.begin(), cands.end(), a) - cands.end();
        int ub = upper_bound(cands.begin(), cands.end(), b) - cands.end();
        printf("%d\n", ub - lb);
    }
    return 0;
}