フェーン現象 (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<A_{i+1}$由于海拔升高,风的温度会下降$(A_{i+1}-A_i)\times S$度 ###### 输入格式： 从标准输入中读入下面的数据. - 第一行输入包括四个被空格隔开的整数$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$位置的风的温度)

[problemUrl]: https://atcoder.jp/contests/joi2017ho/tasks/joi2017ho_a

標準入力から以下の入力を読み込め． - $ 1 $ 行目には， $ 4 $ 個の整数 $ N,\ Q,\ S,\ T $ が空白を区切りとして書かれている．これらは，JOI 君の家が地点 $ N $ に建てられており，地殻変動の回数が $ Q $ であり，標高が $ 1 $ 上がるごとに風の温度が $ S $ 度下がり，$ 1 $ 下がるごとに $ T $ 度上がることを表す． - 続く $ N\ +\ 1 $ 行のうちの $ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ N\ +\ 1 $) には，地点 $ i\ +\ 1 $ での地殻変動が起こる前の標高を表す整数 $ A_{i\ -\ 1} $ が書かれている． - 続く $ Q $ 行のうちの $ j $ 行目 ($ 1\ \leqq\ j\ \leqq\ Q $) には，$ 3 $ 個の整数 $ L_j,\ R_j,\ X_j $ が空白を区切りとして書かれている．これらは，$ j $ 日目の地殻変動で地点 $ L_j $ から $ R_j $ までの標高が $ X_j $ だけ変化することを表す．

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

3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

-5
-7
-13
-13
-18

2 2 5 5
0
6
-1
1 1 4
1 2 8

5
-35

7 8 8 13
0
4
-9
4
-2
3
10
-9
1 4 8
3 5 -2
3 3 9
1 7 4
3 5 -1
5 6 3
4 4 9
6 7 -10

277
277
322
290
290
290
290
370

### 課題 地殻変動が起きる前の標高と地殻変動の情報が与えられたとき，すべての整数 $ 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 $ の条件を満たす． - - - - - -