本文共 982 字，大约阅读时间需要 3 分钟。

牛客小白月赛5 I.区间 (interval)

题目描述

Apojacsleam喜欢数组。他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：    操作一：将a[L]-a[R]内的元素都加上P    操作二：将a[L]-a[R]内的元素都减去P最后询问a[l]-a[r]内的元素之和？请认真看题干及输入描述。

输入描述:

输入共 $M+3$ 行：

第一行两个数，n，M，意义如“题目描述”

第二行 n 个数，描述数组。

下面共 $M$ 行，每行四个数，q，L，R，P，若 $q$ 为1则表示执行操作2，否则为执行操作1

最后一行，两个正整数 l，r

输出描述:

一个正整数，为 $a[l]-a[r]$ 内的元素之和

示例1

输入

10 51 2 3 4 5 6 7 8 9 101 1 5 51 2 3 60 2 5 5 0 2 5 81 4 9 62 7

输出

23

典型的离散思想求前缀和即可，注意题目保证输入是 $int$，但并没有保证输出也在 $int$ 范围内，AC代码如下：

#include
   
    using namespace std;typedef long long ll;const int N=1e6+5;int n,m,op,l,r;ll p,x,ans,a[N],sum[N];int main(){
       scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);    while(m--){
           scanf("%d%d%d%lld",&op,&l,&r,&p);        if(op==1) sum[l]-=p,sum[r+1]+=p;        else sum[l]+=p,sum[r+1]-=p;    }    scanf("%d%d",&l,&r);    for(int i=1;i<=n;i++){
           x+=sum[i];        if(i>=l&&i<=r) ans+=x+a[i];    }    printf("%lld",ans);}
   

转载地址：https://zaizai.blog.csdn.net/article/details/108166144 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！