【0】题解：P11790 [JOI 2017 Final] 焚风现象 / Foehn Phenomena【差分】

ExFish · 2025-02-25 12:35:42 · 题解

考虑维护前缀和。

首先，我们按照题意即可求出初始温度 tpr。

接着，在每一次更新后，我们考虑动态维护当前点 n 的温度。

首先是左端点。

我们首先要把原先的温度记录清空，tpr\to tpr-f(d_l)，这里 f(x) 表示高度变化的温度贡献。

然后加回去，tpr\to tpr+f(d_l+x)。

注意要对 d_l 也修改。

对于右端点操作同理。

注意：当 r+1>n，我们修改的前缀和是无法影响 n 温度的，那么不要修改。

最后输出即可。

双倍经验。

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N=2e5+10;
int n,Q,S,T,a[N],d[N],L,R,x;
int get(int x){
    if(x<0)return -x*T;
    else return -x*S;
}
signed main(){
    cin>>n>>Q>>S>>T;
    int tpr=0;
    for(int i=0;i<=n;i++){
        cin>>a[i];if(i==0)continue;
        d[i]=a[i]-a[i-1];
        tpr+=get(d[i]);
    }
    while(Q--){
        cin>>L>>R>>x;
        tpr-=get(d[L]);tpr+=get(d[L]+x);
        d[L]+=x;
        if(R+1>n){cout<<tpr<<endl;continue;}
        tpr-=get(d[R+1]);tpr+=get(d[R+1]-x);
        d[R+1]-=x;
        cout<<tpr<<endl;
    }
    return 0;
}