题解

本题使用差分数组解决区间修改问题。

算法思路：

1. 差分数组构造：

   • 定义差分数组 $d[i] = a[i-1] - a[i]$，表示相邻两项的差值
   • 初始化时计算所有差分值，并根据正负性累加到答案中：
     • 若 $d[i] < 0$，贡献为 $d[i] \times s$
     • 若 $d[i] \geq 0$，贡献为 $d[i] \times t$

2. 区间修改的本质：

   • 对区间 $[l, r]$ 整体加 $x$，相当于：
     • $a[l], a[l+1], \ldots, a[r]$ 都加上 $x$
   • 在差分数组中的影响：
     • $d[l] = a[l-1] - a[l]$ 会减少 $x$（即 $d[l] -= x$）
     • $d[r+1] = a[r] - a[r+1]$ 会增加 $x$（即 $d[r+1] += x$）
     • 其他位置的差分值不变

3. 动态维护答案：

   • 每次修改前，先将 $d[l]$ 和 $d[r+1]$ 的贡献从答案中减去
   • 更新差分值后，再将新的贡献加回答案
   • 注意边界情况：若 $r+1 > n$，则不需要修改 $d[r+1]$

时间复杂度：$O(n + q)$，每次查询 $O(1)$ 完成。

这是差分数组的经典应用，将区间修改转化为单点修改。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const ll N=2e5+10;
ll n,q,s,t;
ll a[N];
ll d[N];
ll ans=0; 
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin>>n>>q>>s>>t; 
//	s=-s;t=-t;
	for(int i=0;i<=n;i++){
		cin>>a[i];
		if(i>0){
			d[i]=a[i-1]-a[i];
//			d[i]=-d[i]; 
			if(d[i]<0) ans+=d[i]*s;
			else ans+=d[i]*t; 
		}
	}
	while(q--){
		ll l,r,x;
		cin>>l>>r>>x;
		if(d[l]<0) ans-=d[l]*s;
		else ans-=d[l]*t;
		d[l]-=x;
		if(d[l]<0) ans+=d[l]*s;
		else ans+=d[l]*t;
		if(r+1>n){
			cout<<ans<<"\n";
			continue;
		} 
		if(d[r+1]<0) ans-=d[r+1]*s;
		else ans-=d[r+1]*t;
		d[r+1]+=x;
		if(d[r+1]<0) ans+=d[r+1]*s;
		else ans+=d[r+1]*t;
		cout<<ans<<"\n";
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}
//qwq