#2332. 「JOI 2017 Final」焚风现象

内存限制:256 MiB 时间限制:200 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOI 2017 Final T1「フェーン現象 / Foehn Phenomena

焚风是是由于空气作绝热下沉运动时,因温度升高湿度降低而形成的一种干热风。焚风常出现在山脉背风坡,由山地引发的过山气流在背风坡下沉,使过山气流变得干热的一种风。在高压区,空气下沉也可产生焚风。

IOI 王国永远刮着海风。风从地点 0 依次吹到地点 1 ,地点 2 ……直到地点 N ,共 N+1 个地点。JOI 君住在地点 N 。地点 0 的海拔 A_0=0 ,地点 i 的海拔为 A_i
地表风的温度随海拔升降而变化。地点 0 在海边,温度为 0 度;对于任一地点 i ,从地点 i 吹到地点 i+1 的风的温差仅取决于两地的海拔差。具体来说:

  • 如果 A_i=A_{i+1} ,风的温度不变;
  • 如果 A_i<A_{i+1} ,风每爬升 1 米,温度就会下降 S 度;
  • 如果 A_i> A_{i+1} ,风每下沉 1 米,温度就会升高 T 度。

IOI 国的地壳运动很强烈。你得到了 Q 天来地壳运动的数据。在第 j 日,地点 L_j, L_j+1, \ldots, R_j 的海拔升高了 X_j ,注意 X_j 可能是负数。
你的任务是,计算每天地壳运动后 JOI 君住所的温度。

输入格式

第一行有四个整数 N, Q, S, T ,用空格分隔。
在接下来的 N+1 行中,第 i (1\leqslant i\leqslant N+1) 有一个整数 A_{i-1}
在接下来的 Q 行中,第 j (1\leqslant j\leqslant Q) 有三个整数 L_j, R_j, X_j ,用空格分隔。
输入的所有数的含义见题目描述。

输出格式

Q 行,第 j (1\leqslant j\leqslant Q) 有一个整数,表示第 j 日地壳运动后 JOI 君住所的温度。

样例

样例输入 1

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

样例输出 1

-5
-7
-13
-13
-18

样例解释 1

最初,地点 0,1,2,3 的海拔分别是 0,4,1,8 。第一天地壳运动后,海拔分别为 0,6,3,8 。 此时,风的温度分别为 0,-6,0,-5

样例输入 2

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

样例输出 2

5
-35

样例输入 3

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

样例输出 3

277
277
322
290
290
290
290
370

数据范围与提示

对于 30\% 的数据, N, Q\leqslant 2000
对于另外 10\% 的数据, S=T
对于所有数据, 1\leqslant N, Q\leqslant 2\times 10^5, 1\leqslant S, T\leqslant 10^6; A_0=0, |A_i|\leqslant 10^6(1\leqslant i\leqslant N); 1\leqslant L_j\leqslant R_j\leqslant N, |X_j|\leqslant 10^6 (1\leqslant j\leqslant Q)