题解：SP28265 ADARAIN - Ada and Rain

题目大意

给一个长为

W

的数组，对其进行

N

个操作，每次将

[L,R]

的区间加上

1

，操作后进行

M

个查询，每次查询数组中下标为

a

的数值。

题目分析

题目中数据保证

0 \le N,M \le 10^5

，若直接用暴力，复杂度为

O(MW)

，显然会超时，所以可以采用差分的方法，每次，对数组进行操作时直接将下标为

L

的数值加

1

，将下标为

R + 1

的数值减

1

，求一遍前缀和即可，复杂度为

O(M)

。

Code

CPP

#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记录。

题解：SP28265 ADARAIN - Ada and Rain

文章操作

题目大意

题目分析

Code

相关推荐

评论

题解：SP28265 ADARAIN - Ada and Rain