题解 AT2442 【フェーン現象 (Foehn Phenomena)】
顾z
2018-10-14 19:42:48
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
原题为「JOI 2017 Final」焚风现象
题解的话如果你们看得懂日文就去看看 -->[https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-t1-review.pdf](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-t1-review.pdf)
### 分析
首先,这是一个**差分模板题**,不过应该不是很容易看出来.
涉及到了**区间修改与单点查询**.(我相信有人会写数据结构的.
但是这里的单点查询就是一个固定的点$n$。
#### 首先考虑为什么可以差分去做?
~~题目中的描述就暗示着我们进行差分啊.~~
首先我们发现了题目中的这一句话
> 风的温度随海拔升降而变化。
而,每个地点的海拔已知,所以我们可以在输入的时候求出每个位置的海拔差.
#### 做法
根据海拔差,我们又可以求出每个位置的温度.由于$n$位置不会变,且一直为最后一个位置.
所以我们可以累加$ans$.(因为最后一个位置$n$永远不会变。
而且考虑到某一段区间的海拔变化,相对位置不会变,我们只需要考虑从起始位置$l$的温度变化,后面到达$r$的温度就随之变化.
这里需要注意的位置就是当$r==n$的时候,是不需要变化$r+1$位置的海拔与温度的.
即我们的$ans$是不需要改变的.而改变的话,需要考虑相对高度的变化.我相信大家能懂的 qwq.
### 代码
```c++
#include<cstdio>
#include<cstring>
#include<cctype>
#define N 200005
#define R register
using namespace std;
long long n,q,s,t;
long long A[N],last,ans;
inline void in(long long &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;
}
inline long long get(long long x)
{
return x > 0 ? -(x*s) : -(x*t) ;
}
int main()
{
//freopen("cure.in","r",stdin);
//freopen("cure.out","w",stdout);
in(n),in(q),in(s),in(t);
in(last);
for(R int i=1;i<=n;i++)
{
R long long x;
in(x);
A[i]=x-last;
last=x;
ans+=get(A[i]);
}
for(R long long x,y,z;q;q--)
{
in(x),in(y),in(z);
ans-=get(A[x]);
A[x]+=z;
ans+=get(A[x]);
if(y!=n) ans-=get(A[y+1]),A[y+1]-=z,ans+=get(A[y+1]);
printf("%lld\n",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}
```
还有标程~~很神奇~~
```c++
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll s1,s2;
ll dif[300001];
ll get(ll t)
{
if(t>0)return -s1*t;
else return -s2*t;
}
int main()
{
int num,query;
scanf("%d%d%lld%lld",&num,&query,&s1,&s2);
vector<int>v;
for(int i=0;i<=num;i++)
{
int z;
scanf("%d",&z);
v.push_back(z);
}
ll ans=0;
for(int i=0;i<num;i++)
{
dif[i]=v[i+1]-v[i];
ans+=get(dif[i]);
}
for(int i=0;i<query;i++)
{
int za,zb,zc;
scanf("%d%d%d",&za,&zb,&zc);
ans-=get(dif[za-1]);
dif[za-1]+=zc;
ans+=get(dif[za-1]);
if(zb!=num)
{
ans-=get(dif[zb]);
dif[zb]-=zc;
ans+=get(dif[zb]);
}
printf("%lld\n",ans);
}
}
```