题解 P3655 【不成熟的梦想家 (未熟DREAMER)】
顾z
2018-10-15 06:55:34
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
这题就是$JOI\ 2017$焚风现象啊 qwq
首先,这是一个**差分模板题**,不过应该不是很容易看出来.
涉及到了**区间修改与单点查询**.(我相信有人会写数据结构的.
但是这里的单点查询就是一个固定的点$n$。
#### 首先考虑为什么可以差分去做?
~~题目中的描述就暗示着我们进行差分啊.~~
首先我们发现了题目中的变化规则
> 当$A_{i-1}< A_i$,$B=B-S|A_{i-1}-A_i|$
> 当$A_{i-1}> A_i$,$B=B+T|A_{i-1}-A_i|$
而,每个人的唱功$A_i$已知,所以我们可以在输入的时候求出每个位置的唱功差.
#### 做法
根据唱功差,我们又可以求出每个位置的魅力值.由于$n$位置不会变,且一直为最后一个位置.
所以我们可以累加$ans$.(因为最后一个位置$n$永远不会变。
而且考虑到某一段区间的唱功变化,相对位置不会变,我们只需要考虑从起始位置$l$的魅力值变化,后面到达$r$的魅力值就随之变化.
这里需要注意的位置就是当$r==n$的时候,是不需要变化$r+1$位置的唱功与魅力值的.
即我们的$ans$是不需要改变的.而改变的话,需要考虑相对唱功的变化.我相信大家能懂的 qwq.
``代码``
```cpp
#include<cstdio>
#include<cctype>
#define int long long
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int N,Q,S,T,ans,last,A[200008];
inline int calc(int x)
{
return x>0 ? -S*x:-T*x;
}
signed main()
{
in(N),in(Q),in(S),in(T);
for(R int i=0,x;i<=N;i++)
{
in(x);
A[i]=x-last;
ans+=calc(A[i]);
last=x;
}
for(R int i=1,x,y,z;i<=Q;i++)
{
in(x),in(y),in(z);
ans-=calc(A[x]);A[x]+=z;ans+=calc(A[x]);
if(y!=N)ans-=calc(A[y+1]),A[y+1]-=z,ans+=calc(A[y+1]);
printf("%lld\n",ans);
}
}
```