题解 AT2442 【フェーン現象 (Foehn Phenomena)】
要做这个题，首先我们要了解一个概念：差分
差分是个啥？好多同学肯定一听这高大上的名字就晕了，其实差分这东西，你也不用想得太神秘，把第二个字去掉，这差分其实就是个“差”
那具体是什么样的“差”呢？就是数组元素中，每两项之间的差（特别的，差分数组的第一项原数组的第一项自己）
栗子：
原数组： 5 2 0 1 3 1 4
每两项的差： 2-5=-3 0-2=-2 1-0=1 3-1=2 1-3=-2 4-1=3
差分数组：5 -3 -2 1 2 -2 3话说回来，这题到底跟这差分有啥关系呢？？先说这题的核心操作
......接下来的
Q 行中第j 行(1\leq j\leq Q) 包括三个被空格隔开的整数L_j,R_j,X_j .这表示第j 天地壳运动使地点L_j 到地点R_j 中这些地点的海拔变化了X_j
emmmmm......区间修改
......输出
Q 行,第j 行的输出代表第j 天地壳运动后N 位置的风的温度
emmmmm......查询操作
这两个词一出现，大家有没有条件反射般地想到什么东西呢？也许做过树状数组2的同志们可能已经晓得了：我们当初用树状数组进行区间修改和单点查询操作的时候，存在树状数组里的值的就是数组元素之间的差分！
（说句闲话，我一开始想到这里本来想用树状数组做来着，结果怎么写也写不出来，后来才发现这题更简单——压根用不着树状数组！）
那用差分进行区间修改操作的时候，好处都有啥？咱这就讲：
（如果你已经AC了树状数组2或已经了解过这部分内容，你就可以跳过啦！）
咱还是从一个栗子开始：
将数组5 2 0 1 3 1 4，将2~5区间内的每个数加上6
加上之后，求出差分，和原数组对比一下：
| 原数组 | 5 2 0 1 3 1 4 |
| 修改后的数组 | 5 8 6 7 9 1 4 |
| 原差分数组 | 5 -3 -2 1 2 -2 3 |
| 修改后的差分数组 | 5 3 -2 1 2 -8 3 |
简直“没有对比就没有伤害”啊，如果直接在原数组上动工，那就要修改好多好多个，而修改差分数组，只需要修改两个就行啦！
为什么呢？这一切的功劳就在于我们数学课本里等式的性质：如果两个数加上或减去一个数，等式仍然成立
如果
所以如果当两个数
现在明白差分为啥有这么神奇的威力了吧！并且，经过大量的举例和推导，我们可以得到差分变化的规律是这样的：
a[l]+=k;
a[r+1]-=k;不仅如此题目中温度的变化也跟海拔差有关，所以差分当然是这个题的最好选择啦！
那这样的话，这个题的思路就有啦！废话不多说，先上代码！
等会，在放代码之前，咱先来介绍一下这个函数（逃）：
int read(){
char c=getchar();
int f=1,x=0;
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}没错这就是大名鼎鼎的读入优化！（俗称“快读”）
因为刚学会嘛，所以顺便在这篇题解里给大家讲讲这玩意怎么写（会快读的可以跳过啦）：
大家都知道，scanf比cin快得可不是一点半点，（亲测：cin TLE了五六个点，scanf全A）那有比scanf更快的吗？
当然有喽！就是大名鼎鼎的getchar()
所以这个读入优化的原理就是每次把数据以字符的形式读进去再转化成int类型!
明白了这一点，就可以知道怎么搞这个东西了：
int read(){
char c=getchar(); //先读入一个字符
int f=1,x=0;//f是这个数的符号（正负），x是这个数
while(c<'0'||c>'9'){ //如果不是数字的话（就是负号呗）
if(c=='-')
f=-1; //这个数是负数了
c=getchar();
}
while(c>='0'&&c<='9'){ //是数字就接着往下读
x=(x<<1)+(x<<3)+(c^'0');
//其实就相当于x*10+c-'0'，x<<n是指x*2的n次方，x*2+x*8不就是x*10嘛，至于c^0，实际上就是c-'0'，用二进制位运算可以加快速度
c=getchar();
}
return x*f; //返回读入的x*数的符号f
}这样的话我们就可以安心写代码啦！
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll; //十年OI一场空，不开 long long见祖宗
ll a[4000005];//差分数组
ll n,q,s,t;//不解释
inline ll read(){
//快读！（代码里的inline和下文for循环里的“register”一样，只是优化用的，完全可以去掉）
char c=getchar();
int f=1;
ll x=0;
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
ll temp(ll x){//这个函数是来求变化温度的，根据题意模拟即可
if(x>=0)
return -x*s;
else return -x*t; //因为海拔方向和温度方向相反，所以要加个负号
}
int main(){
n=read();q=read();s=read();t=read(); //快读，实在不会的可以用scanf代替
ll last=0; //last用来存储上一个数（不理解？看下面）
for(register int i=0;i<=n;i++){//注意这题是从0开始存
ll k=read(); //读入当前数据
a[i]=k-last; //数组中存储两个元素的差（差分）
last=k; //更新last
}
for(register int i=1;i<=q;i++){
ll l=read(),r=read(),k=read();//没啥好说的
a[l]+=k; //根据前面得到的结论进行差分数组的修改
a[r+1]-=k;
ll ans=0; //记录最后输出的答案
for(register int j=0;j<=n;j++)
ans+=temp(a[j]); //对每个海拔的变化值（差分）求温度，加起来，输出，perfect!
printf("%lld\n",ans);
}
return 0;
}交上去一看......葡萄美酒夜光杯，T了一堆又一堆
为啥呢？我分析了一下：每一次修改时，都要遍历整个数组，太慢！
那咋办呢？？后来我（通过看题解）发现，反正每次修改就需要改两个数，所以我们只需要把变化的高度求出来更新在ans变量里就好啦！
嗯，这思路不错嘛，还有一点要注意的：当r=n的时候，我们不需要更新差分数组的值，记住了这几点，我们把代码修改成这样
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll a[4000005];
ll n,q,s,t;
ll ans=0;
inline ll read(){
char c=getchar();
int f=1;
ll x=0;
while(c<'0'||c>'9'){
if(c=='-')
f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x*f;
}
ll temp(ll x){
if(x>=0)
return -x*s;
else return -x*t;
}
int main(){
n=read();q=read();s=read();t=read();
ll last=0;
for(register int i=0;i<=n;i++){
ll k=read();
a[i]=k-last;
last=k;//到这里和前面都一样
ans+=temp(a[i]);//注意第一次输入就可以顺道把没有经过地壳运动的初始ans记录下来哦！
}
for(register int i=1;i<=q;i++){
ll l=read(),r=read(),k=read();
//在修改差分数组的时候，顺便进行ans的更新
ans-=temp(a[l]); //旧的不去，新的不来！
a[l]+=k;
ans+=temp(a[l]);//更新后的值再加到ANS里面
if(r<n){ //特判r要小于n
ans-=temp(a[r+1]);//对右端点也如法炮制
a[r+1]-=k;
ans+=temp(a[r+1]);
}
printf("%lld\n",ans);
}
return 0;
}于是就愉快的AC了
好了总结一下：这次我们学了一个新技能，叫差分，它是数组里每两个元素之间的差，在区间修改里可以起到大作用！最后还要注意时间的优化哦！
The End!!!