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

该题解为本人第一篇题解，如有需改进的地方，请告诉我，谢谢！

部分分：

对于 Subtask

1

：直接暴力即可。

对于 Subtask

2

：

a_n \times s

即为答案。

正解思路：

本题频繁性对区间操作，很自然地我们会想到差分。

~~不过这题用不用差分都差不多，只是用差分代码更简洁。~~

由于最多有

2 \times 10^5

天，所以计算每天的时间复杂度必须为

O(1)

。我们可以想到：必须每次操作维护

\text{ans}

，而不是完全依赖于差分数组。

对于每次操作的区间起点和终点：

$\text{ans}$ 减去风改变的值。
修改差分数组。
$\text{ans}$ 加上现在风改变的值。

（如果终点小于

n

可以不用处理终点）

所以其实这里差分数组唯一作用就是用更简洁的语言代替

a_l-a_{l-1}

。

代码：

CPP

#include<iostream>
#include<cstdio>
using namespace std;
const int NR=200010;
int a[NR];
long long b[NR];
int main()
{
	int n,q,s,t,i;
	cin>>n>>q>>s>>t;
	long long ans=0;
	for(i=0;i<=n;i++)
	{
		cin>>a[i];
		if(i!=0) b[i]=a[i]-a[i-1];
		if(i!=0 && a[i]>a[i-1])	ans+=b[i]*(-s);
		else if(i!=0 && a[i]<a[i-1]) ans+=-b[i]*t; 
	}
	while(q--)
	{
		int l,r,x;
		cin>>l>>r>>x;
		if(b[l]>0) ans-=b[l]*(-s);
		else ans-=-b[l]*t;
		b[l]+=x;
		if(b[l]>0) ans+=b[l]*(-s);
		else ans+=-b[l]*t;
		if(r<n)
		{
			if(b[r+1]>0) ans-=b[r+1]*(-s);
			else ans-=-b[r+1]*t;
			b[r+1]-=x;
			if(b[r+1]>0) ans+=b[r+1]*(-s);
			else ans+=-b[r+1]*t;
		}
		cout<<ans<<endl;
	}
	return 0;
}

注意事项：

在这里：

CPP

if(b[l]>0) ans-=b[l]*(-s);
else ans-=-b[l]*t;
b[l]+=x;

b_1

可能一开始为正（即

a_l>a_{l-1}

），但后面可能让

b_1

变为负，所以

\text{ans}

必须先减后加。

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

文章操作

部分分：

正解思路：

代码：

注意事项：

相关推荐

评论

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