NC16722. 区间 (interval)
描述
Apojacsleam喜欢数组。
他现在有一个n个元素的数组a，而他要对a[L]-a[R]进行M次操作：
操作一：将a[L]-a[R]内的元素都加上P
操作二：将a[L]-a[R]内的元素都减去P
输入描述
输入共M+3行：
第一行两个数，n，M，意义如“题目描述”
第二行n个数，描述数组。
第3-M+2行，共M行，每行四个数，q，L，R，P，若q为1则表示执行操作2，否则为执行操作1
第4行，两个正整数l，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
说明:
C++14(g++5.4) 解法, 执行用时: 802ms, 内存消耗: 15960K, 提交时间: 2018-07-23 19:23:58
#include<cstdio>
long long a[1000001],c[1000001],n,m,l,r,p,q;
int main() {
scanf("%lld%lld",&n,&m);
for( int i=1;i<=n;i++)
scanf("%lld",&a[i]);
for( int i=1;i<=m;i++)
{ scanf("%lld%lld%lld%lld",&q,&l,&r,&p);
if(q==1) p=-p; c[l]+=p;c[r+1]-=p; }
for( int i=1;i<=n;i++)
{ c[i]+=c[i-1]; a[i]+=c[i]+a[i-1]; }
scanf("%lld%lld",&l,&r);
printf("%lld\n",a[r]-a[l-1]);
return 0; }
C++(clang++11) 解法, 执行用时: 1243ms, 内存消耗: 22968K, 提交时间: 2020-11-29 11:44:02
#include<iostream>
using namespace std;
int main(){
long long q,L,R,p;
long long n,m;
long long a[1000005],b[1000005]={0};
long long i;
cin>>n>>m;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<m;i++){
cin>>q>>L>>R>>p;
if(q==1) p=-p;
b[L-1]+=p;
b[R]-=p;
}
for(i=1;i<n;i++){
b[i]+=b[i-1];
}
long long t1,t2,t3=0;
cin>>t1>>t2;
for(i=t1-1;i<t2;i++)
t3+=a[i]+b[i];
cout<<t3;
}