差分 A - フェーン現象 (Foehn Phenomena)

题目来源AtCoder

评测方式RemoteJudge

难度普及+/提高

时间限制1.00s

内存限制256.00MB

题目描述

输入格式

標準入力から以下の入力を読み込め．

• 11?行目には，?44?個の整数?N,\ Q,\ S,\ TN,?Q,?S,?T?が空白を区切りとして書かれている．これらは，JOI 君の家が地点?NN?に建てられており，地殻変動の回数が?QQ?であり，標高が?11?上がるごとに風の温度が?SS?度下がり，11?下がるごとに?TT?度上がることを表す．
• 続く?N\ +\ 1N?+?1?行のうちの?ii?行目 (1\ \leqq\ i\ \leqq\ N\ +\ 11?≦?i?≦?N?+?1) には，地点?i\ +\ 1i?+?1?での地殻変動が起こる前の標高を表す整数?A_{i\ -\ 1}Ai???1??が書かれている．
• 続く?QQ?行のうちの?jj?行目 (1\ \leqq\ j\ \leqq\ Q1?≦?j?≦?Q) には，33?個の整数?L_j,\ R_j,\ X_jLj?,?Rj?,?Xj??が空白を区切りとして書かれている．これらは，jj?日目の地殻変動で地点?L_jLj??から?R_jRj??までの標高が?X_jXj??だけ変化することを表す．

输出格式

出力は?QQ?行からなる．標準出力の?jj?行目 (1\ \leqq\ j\ \leqq\ Q1?≦?j?≦?Q) には，jj?日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を出力せよ．

?

题意翻译

题目简述

你知道N+1个地点的海拔Ai?,编号为0…N,有风从0吹向N,想让你求出地点N的风的温度.

保证A0=0

规则：

• 如果Ai=Ai+1?风的温度不变.
• 如果Ai?>Ai+1?由于海拔降低,风的温度会上升(Ai??Ai+1?)×T度
• 如果Ai?<Ai+1?由于海拔升高,风的温度会下降(Ai+1??Ai?)×S度

输入格式：

从标准输入中读入下面的数据.

• 第一行输入包括四个被空格隔开的整数N,Q,S,T.这表示JOI先生在地点N有一所房子,有Q次地壳运动,海拔每上升1米的话,风的温度会降低S度,海拔每下降一米的话,风的温度会上升T度.
• 接下来的N+1行中第i行(1≤i≤N+1)包含一个整数Ai?1?,表示地壳运动前地点i?1的海拔高度.
• 接下来的Q行中第j行(1≤j≤Q)包括三个被空格隔开的整数Lj?,Rj?,Xj?.这表示第j天地壳运动使地点Lj?到地点Rj?中这些地点的海拔变化了Xj?

输出格式:

输出Q行,第j行的输出代表第jj天地壳运动后JOI先生家的风的温度. (即N位置的风的温度)

题解：

用差分

上代码

?

?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll n,q,s,t,a[N],l[N],r[N],x[N],d[N],sum;
int main(){
	cin>>n>>q>>s>>t;
	for(int i=0;i<n+1;i++){
		cin>>a[i];
	}
	for(int i=1;i<n+1;i++){
		d[i]=a[i]-a[i-1];
	}
	for(int j=1;j<q+1;j++){
		cin>>l[j]>>r[j]>>x[j];
	}
	for(int i=1;i<n+1;i++){
		if(d[i]>0){
			sum-=d[i]*s;
		}else if(d[i]<0){
			sum-=d[i]*t;
		}
	}
	for(int k=1;k<q+1;k++){
		if(d[l[k]]>0){
			sum+=d[l[k]]*s;
		}else if(d[l[k]]<0){
			sum+=d[l[k]]*t;
		}
		d[l[k]]+=x[k];
		if(d[l[k]]>0){
			sum-=d[l[k]]*s;
		}else if(d[l[k]]<0){
			sum-=d[l[k]]*t;
		}
		if(r[k]==n){
			cout<<sum<<endl;
			continue;
		}
		if(d[r[k]+1]>0){
			sum+=d[r[k]+1]*s;
		}else if(d[r[k]+1]<0){
			sum+=d[r[k]+1]*t;
		}
		d[r[k]+1]-=x[k];
		if(d[r[k]+1]>0){
			sum-=d[r[k]+1]*s;
		}else if(d[r[k]+1]<0){
			sum-=d[r[k]+1]*t;
		}
		cout<<sum<<endl;
	}
	return 0;
}

?