题解：SP28265 ADARAIN - Ada and Rain

woshizhangchi123 · 2025-07-18 15:49:29 · 题解

题目大意

给一个长为 W 的数组，对其进行 N 个操作，每次将 [L,R] 的区间加上 1，操作后进行 M 个查询，每次查询数组中下标为 a 的数值。

题目分析

题目中数据保证 0 \le N,M \le 10^5 ，若直接用暴力，复杂度为 O(MW)，显然会超时，所以可以采用差分的方法，每次，对数组进行操作时直接将下标为 L 的数值加 1，将下标为 R + 1 的数值减 1，求一遍前缀和即可，复杂度为 O(M)。

Code

#include <bits/stdc++.h>
using namespace std;
int n,q,m,x,y,l[10010000];
int main() {
    cin>>n>>q>>m;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        l[x]++;l[y+1]--;
    }
    for(int i=1;i<=m;i++){
        l[i]+=l[i-1];
    }
    for(int i=1;i<=q;i++){
        cin>>x;
        cout<<l[x]<<"\n";
    }
}

AC记录。