前后缀和|牛客小白月赛5 I.区间 (interval) 前后缀和|牛客

牛客小白月赛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 M+3 M+3 行：
第一行两个数，n，M，意义如“题目描述”
【前后缀和|牛客小白月赛5 I.区间 (interval)】第二行 n 个数，描述数组。
下面共M M M 行，每行四个数，q，L，R，P，若q q q 为1则表示执行操作2，否则为执行操作1
最后一行，两个正整数 l，r
输出描述: 一个正整数，为a [ l ] ? a [ r ] a[l]-a[r] a[l]?a[r] 内的元素之和
示例1 输入

10 5 1 2 3 4 5 6 7 8 9 10 1 1 5 5 1 2 3 6 0 2 5 5 0 2 5 8 1 4 9 6 2 7

输出

23

典型的离散思想求前缀和即可，注意题目保证输入是i n t int int，但并没有保证输出也在i n t 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); }