P3655 不成熟的梦想家 (未熟DREAMER) 题解

风急风也清 · 2021-12-06 14:02:23 · 题解

发现最近我好像一直在打差分的题解。

根据题目描述中的：每次把第 X 个到第 Y 个加上 Z 时！

我们就可以瞬间想到，此题可以使用差分！

什么是差分？ 差分就是批量对区间整体操作。

方法：

在 d_{x} 上加上 z 会让后面的学生全部加上 z。

但这时把后面全部都加了，因此多算了，要减掉一节,也就是从 d_{y+1} 后开始减去 z。

把两个综合起来就是我们所需要的差分大法公式，如果不大理解的，可以试着自己画图推导一下。

最后要注意一下样例的数据，是不是该开个 long long 了？

综上所述，整合代码如下：

#include<bits/stdc++.h>
using namespace std;
long long d[200005];
long long n,q,s,t,ans=0;
long long f(long long k)  //因为下面需要用到很多次这玩意，因此可整个函数。
{
    if(k<0) return -t*k;
    else return -s*k;
}
int main()
{
    long long b=0;
    cin>>n>>q>>s>>t;
    for(int i=0;i<=n;i++)
    {
        long long a;
        cin>>a;
        if(i>0) d[i]=a-b,b=a; //存每个数之间的差。    
        ans+=f(d[i]);  //将一开始的结果存一下。
    }
    for(int i=1;i<=q;i++)
    {
        long long x,y,z;
        cin>>x>>y>>z;
        ans-=f(d[x]);  //以下都是差分大法。
        d[x]+=z;
        ans+=f(d[x]);
        if(y<n)
          { ans-=f(d[y+1]); d[y+1]-=z; ans+=f(d[y+1]); }
        cout<<ans<<endl;
    }
    return 0;     
}