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

我们首先看数据范围，数据范围

N \le 2 \times 10^5,Q \le 2 \times 10^5

考虑

O(n \log n)

或者

O(n)

算法。

我们看到区间修改，想到差分。

此时差分数组代表目前海拔与上个海拔的差。

因为计算式中只与差有关，所以差分数组正好只需要考虑左端的

l

与右端的

r+1

。

此时考虑正负状态。

设差分数组为

a

。

先模拟出初始的答案。

此后就只需要

O(1)

判断即可。

左端有四种情况：

如果此时 $a_l \geq 0$ 且 $a_l + p \geq 0$ ，那么左端答案就是上一次的答案减少 $p \times s$ 。
如果此时 $a_i \geq 0$ 且 $a_i + p \leq 0$ ，那么左端答案就是上一次的答案减到零还要再减一部分就是加上 $a_l \times s - （p + a_l） \times t$ 。
如果此时 $a_i \leq 0$ 且 $a_i + p \geq 0$ ，那么左端答案就是上一次的答案加到零还要再加一部分就是加上 $a_l \times t - （p + a_l） \times s$ 。
如果此时 $a_l \leq 0$ 且 $a_l + p \leq 0$ ，那么左端答案就是上一次的答案减少 $p \times t$ 。

右端同理。

有一个注意点是当右端到 $n$ 的时候对总答案没有影响。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e5+7;
int n,q,s,t,cnt;
int a[N],ans[N];
signed main(){
	cin>>n>>q>>s>>t;
	cin>>a[0];
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>=1;i--)a[i]-=a[i-1];
	for(int i=1;i<=n;i++)if(a[i]>=0)ans[i]=ans[i-1]-a[i]*s;else ans[i]=ans[i-1]-a[i]*t;
	cnt=ans[n];
	for(int i=1;i<=q;i++){
		int l,r,p;
		cin>>l>>r>>p;
		if(a[l]>=0&&a[l]+p>=0)cnt-=p*s,a[l]=a[l]+p;
		else if(a[l]>=0)cnt+=a[l]*s,cnt-=(p+a[l])*t,a[l]=a[l]+p;
		else if(a[l]<=0&&a[l]+p<=0)cnt-=p*t,a[l]=a[l]+p;
		else cnt+=a[l]*t,cnt-=(p+a[l])*s,a[l]=a[l]+p;
		if(r+1<=n){
			if(a[r+1]>=0&&a[r+1]-p>=0)cnt+=p*s,a[r+1]=a[r+1]-p;
			else if(a[r+1]>=0)cnt+=a[r+1]*s,cnt-=(a[r+1]-p)*t,a[r+1]=a[r+1]-p;
			else if(a[r+1]<=0&&a[r+1]-p<=0)cnt+=p*t,a[r+1]=a[r+1]-p;
			else cnt+=a[r+1]*t,cnt-=(a[r+1]-p)*s,a[r+1]=a[r+1]-p;
		}
		cout<<cnt<<endl;
	}
	return 0;
}
// 0 4 -3 7
// 0 6 -3 5
// 0 4 -1 5
// 0 4 4 5

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

文章操作

相关推荐

评论

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