P1065 咖啡温律录 官方题解

【部分分：测试点 1∼41\sim 41∼4】

• 这一档中温度上界只有 $10^3$。一个显然的思路是枚举每一个整数温度 $x$，再扫描全部配方，统计满足 $l_i\leq x\leq r_i$ 的配方数量。数量不少于 $k$ 时，就将 $x$ 标记为已经写入温律录。
• 对一次询问，直接枚举 $[a_j,b_j]$ 中的全部温度并统计标记数量。设温度上界为 $V$，单组数据的时间复杂度为 $\mathcal{O}(V(n+q))$，空间复杂度为 $\mathcal{O}(V)$。

【部分分：测试点 5∼85\sim 85∼8】

• 上一档反复判断一个温度是否落在配方区间中。我们可以考虑使用差分数组，令 $d_{l_i}\gets d_{l_i}+1$，$d_{r_i+1}\gets d_{r_i+1}-1$。求前缀和后，$s_x=\sum_{i=1}^{x}d_i$ 正好表示认可温度 $x$ 的配方数量。
• 再令 $b_x=[s_x\geq k]$，并预处理 $p_x=\sum_{i=1}^{x}b_i$。询问 $[a_j,b_j]$ 的答案就是 $p_{b_j}-p_{a_j-1}$。时间复杂度为 $\mathcal{O}(n+q+V)$，空间复杂度为 $\mathcal{O}(V)$。

【部分分：测试点 9∼129\sim 129∼12】

• 这一档满足 $k=1$，所以温律录恰好是全部配方区间的并。根据这一性质，我们将区间按照左端点排序，依次合并有交集或相邻的区间，可以得到若干两两分离的闭区间。
• 预处理每个合并区间包含的整数数量及其前缀和。一次询问只需二分找到与 $[a_j,b_j]$ 相交的第一个和最后一个合并区间，再处理两侧不完整的部分。时间复杂度为 $\mathcal{O}((n+q)\log n)$，空间复杂度为 $\mathcal{O}(n)$。

【正解】

• 完整数据的温度上界仍然只有 $2\times 10^5$，因此直接使用第二档的差分与两次前缀和即可。第一次前缀和求每个温度被多少张配方认可，第二次前缀和求温律录在任意前缀中包含多少个温度。
• 每个配方只产生两个差分修改，每个询问只进行一次区间作差。单组数据的时间复杂度为 $\mathcal{O}(n+q+V)$，空间复杂度为 $\mathcal{O}(V)$。多组数据之间要清空本组实际使用的数组范围。

【参考代码】

1#include <cstdio>2#include <cstring>3 4#define MAXV 2000105 6using namespace std;7 8int c,T,n,k,q,Diff[MAXV],Pre[MAXV];9 10void Solve() {11    memset(Diff,0,sizeof(Diff));12    memset(Pre,0,sizeof(Pre));13    scanf("%d%d%d",&n,&k,&q);14    for (int i=1,l,r;i<=n;i++) {15        scanf("%d%d",&l,&r);16        Diff[l]++;17        Diff[r+1]--;18    }19    int Now=0;20    for (int i=1;i<MAXV;i++) {21        Now+=Diff[i];22        Pre[i]=Pre[i-1]+(Now>=k);23    }24    for (int i=1,l,r;i<=q;i++) {25        scanf("%d%d",&l,&r);26        printf("%d\n",Pre[r]-Pre[l-1]);27    }28}29 30int main() {31    scanf("%d%d",&c,&T);32    while (T-->0) Solve();33    return 0;34}