题解：P11790 [JOI 2017 Final] 焚风现象 / Foehn Phenomena

Null_in_null · 2025-10-18 11:32:26 · 题解

我们首先看数据范围，数据范围 N \le 2 \times 10^5,Q \le 2 \times 10^5 考虑 O(n \log n) 或者 O(n) 算法。

我们看到区间修改，想到差分。

此时差分数组代表目前海拔与上个海拔的差。

因为计算式中只与差有关，所以差分数组正好只需要考虑左端的 l 与右端的 r+1。

此时考虑正负状态。

设差分数组为 a。

先模拟出初始的答案。

此后就只需要 O(1) 判断即可。

左端有四种情况：

• 如果此时 a_l \geq 0 且 a_l + p \geq 0，那么左端答案就是上一次的答案减少 p \times s。
• 如果此时 a_i \geq 0 且 a_i + p \leq 0，那么左端答案就是上一次的答案减到零还要再减一部分就是加上 a_l \times s - （p + a_l） \times t。
• 如果此时 a_i \leq 0 且 a_i + p \geq 0，那么左端答案就是上一次的答案加到零还要再加一部分就是加上 a_l \times t - （p + a_l） \times s。
• 如果此时 a_l \leq 0 且 a_l + p \leq 0，那么左端答案就是上一次的答案减少 p \times t。

右端同理。

有一个注意点是当右端到 n 的时候对总答案没有影响。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+7;
int n,q,s,t,cnt;
int a[N],ans[N];
signed main(){
    cin>>n>>q>>s>>t;
    cin>>a[0];
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i>=1;i--)a[i]-=a[i-1];
    for(int i=1;i<=n;i++)if(a[i]>=0)ans[i]=ans[i-1]-a[i]*s;else ans[i]=ans[i-1]-a[i]*t;
    cnt=ans[n];
    for(int i=1;i<=q;i++){
        int l,r,p;
        cin>>l>>r>>p;
        if(a[l]>=0&&a[l]+p>=0)cnt-=p*s,a[l]=a[l]+p;
        else if(a[l]>=0)cnt+=a[l]*s,cnt-=(p+a[l])*t,a[l]=a[l]+p;
        else if(a[l]<=0&&a[l]+p<=0)cnt-=p*t,a[l]=a[l]+p;
        else cnt+=a[l]*t,cnt-=(p+a[l])*s,a[l]=a[l]+p;
        if(r+1<=n){
            if(a[r+1]>=0&&a[r+1]-p>=0)cnt+=p*s,a[r+1]=a[r+1]-p;
            else if(a[r+1]>=0)cnt+=a[r+1]*s,cnt-=(a[r+1]-p)*t,a[r+1]=a[r+1]-p;
            else if(a[r+1]<=0&&a[r+1]-p<=0)cnt+=p*t,a[r+1]=a[r+1]-p;
            else cnt+=a[r+1]*t,cnt-=(a[r+1]-p)*s,a[r+1]=a[r+1]-p;
        }
        cout<<cnt<<endl;
    }
    return 0;
}
// 0 4 -3 7
// 0 6 -3 5
// 0 4 -1 5
// 0 4 4 5