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

· · 题解

该题解为本人第一篇题解，如有需改进的地方，请告诉我，谢谢！

部分分：

对于 Subtask 1：直接暴力即可。

对于 Subtask 2：a_n \times s 即为答案。

正解思路：

本题频繁性对区间操作，很自然地我们会想到差分。

不过这题用不用差分都差不多，只是用差分代码更简洁。

由于最多有 2 \times 10^5 天，所以计算每天的时间复杂度必须为 O(1)。我们可以想到：必须每次操作维护 \text{ans}，而不是完全依赖于差分数组。

对于每次操作的区间起点和终点：

  2. 修改差分数组。

（如果终点小于 n 可以不用处理终点）

所以其实这里差分数组唯一作用就是用更简洁的语言代替 a_l-a_{l-1}。

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int NR=200010;
int a[NR];
long long b[NR];
int main()
{
    int n,q,s,t,i;
    cin>>n>>q>>s>>t;
    long long ans=0;
    for(i=0;i<=n;i++)
    {
        cin>>a[i];
        if(i!=0) b[i]=a[i]-a[i-1];
        if(i!=0 && a[i]>a[i-1]) ans+=b[i]*(-s);
        else if(i!=0 && a[i]<a[i-1]) ans+=-b[i]*t; 
    }
    while(q--)
    {
        int l,r,x;
        cin>>l>>r>>x;
        if(b[l]>0) ans-=b[l]*(-s);
        else ans-=-b[l]*t;
        b[l]+=x;
        if(b[l]>0) ans+=b[l]*(-s);
        else ans+=-b[l]*t;
        if(r<n)
        {
            if(b[r+1]>0) ans-=b[r+1]*(-s);
            else ans-=-b[r+1]*t;
            b[r+1]-=x;
            if(b[r+1]>0) ans+=b[r+1]*(-s);
            else ans+=-b[r+1]*t;
        }
        cout<<ans<<endl;
    }
    return 0;
}

注意事项：

在这里：

if(b[l]>0) ans-=b[l]*(-s);
else ans-=-b[l]*t;
b[l]+=x;