loj#2332 「JOI 2017 Final」焚风现象

分析

我们发现改变一个区间实际上只有两个端点的贡献变换

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[200100],s[2],x,y,z,n,m,q,i,j,k,Ans=0;
signed main(){
    scanf("%lld%lld%lld%lld",&n,&q,&s[1],&s[0]);
    for(i=0;i<=n;i++)scanf("%lld",&a[i]);
    for(i=n;i>0;i--)a[i]-=a[i-1],Ans-=a[i]*s[a[i]>0];
    while(q--){
      scanf("%lld%lld%lld",&x,&y,&z);y++;
      Ans+=a[x]*s[a[x]>0]+(y<=n)*a[y]*s[a[y]>0];a[x]+=z,a[y]-=z;
      Ans-=(a[x]*s[a[x]>0]+(y<=n)*a[y]*s[a[y]>0]);printf("%lld
",Ans);
    }
    return 0;
}