AT_joi2017ho_a フェーン現象 (Foehn Phenomena)

### 题目简述 你知道$N+1$个地点的海拔$A_i$,编号为$0 \dots N$,有风从$0$吹向$N$,想让你求出地点$N$的风的温度. 保证$A_0=0$ 规则： - 如果$A_i=A_{i+1}$风的温度不变. - 如果$A_i>A_{i+1}$由于海拔降低,风的温度会上升$(A_i-A_{i+1})\times T$度 - 如果$A_i

从标准输入中读入下面的数据. - 第一行输入包括四个被空格隔开的整数$N,Q,S,T$.这表示JOI先生在地点$N$有一所房子,有$Q$次地壳运动,海拔每上升1米的话,风的温度会降低$S$度,海拔每下降一米的话,风的温度会上升$T$度. - 接下来的$N+1$行中第$i$行$(1\leq i\leq N+1)$包含一个整数$A_{i-1}$,表示地壳运动前地点$i-1$的海拔高度. - 接下来的$Q$行中第$j$行$(1\leq j\leq Q)$包括三个被空格隔开的整数$L_j,R_j,X_j$.这表示第$j$天地壳运动使地点$L_j$到地点$R_j$中这些地点的海拔变化了$X_j$

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

### 課題 地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 $ j $ ($ 1\ \leqq\ j\ \leqq\ Q $) に対し，$ j $ 日目の地殻変動が起こった後の JOI 君の家に吹く風の温度を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 1\ \leqq\ N\ \leqq\ 200\,000 $． - $ 1\ \leqq\ Q\ \leqq\ 200\,000 $． - $ 1\ \leqq\ S\ \leqq\ 1\,000\,000 $． - $ 1\ \leqq\ T\ \leqq\ 1\,000\,000 $． - $ A_0\ =\ 0 $． - $ -1\,000\,000\ \leqq\ A_i\ \leqq\ 1\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ N $)． - $ 1\ \leqq\ L_j\ \leqq\ R_j\ \leqq\ N $ ($ 1\ \leqq\ j\ \leqq\ Q $)． - $ -1\,000\,000\ \leqq\ X_j\ \leqq\ 1\,000\,000 $ ($ 1\ \leqq\ j\ \leqq\ Q $)． ### 小課題 #### 小課題 1 \[30 点\] 以下の条件を満たす． - $ N\ \leqq\ 2\,000 $． - $ Q\ \leqq\ 2\,000 $． #### 小課題 2 \[10 点\] - $ S\ =\ T $ を満たす． #### 小課題 3 \[60 点\] - 追加の制限はない． - - - - - - ### Sample Explanation 1 最初，地点 $ 0,\ 1,\ 2,\ 3 $ の標高はそれぞれ $ 0,\ 4,\ 1,\ 8 $ である．$ 1 $ 日目の地殻変動の後，標高はそれぞれ $ 0,\ 6,\ 3,\ 8 $となる．このとき，地点 $ 0,\ 1,\ 2,\ 3 $ での風の温度はそれぞれ $ 0,\ -6,\ 0,\ -5 $ となる． - - - - - - ### Sample Explanation 2 この入力例は，小課題 $ 2 $ の条件を満たす． - - - - - -