4344: 「JOI 2017 Final」焚风现象
内存限制：256 MB
时间限制：0.200 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
**题目译自 [JOI 2017 Final](https://www.ioi-jp.org/joi/2016/2017-ho/) T1「[フェーン現象](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho.pdf) / [Foehn Phenomena](https://www.ioi-jp.org/joi/2016/2017-ho/2017-ho-en.pdf)」**
> 焚风是是由于空气作绝热下沉运动时，因温度升高湿度降低而形成的一种干热风。焚风常出现在山脉背风坡，由山地引发的过山气流在背风坡下沉，使过山气流变得干热的一种风。在高压区，空气下沉也可产生焚风。
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$ 米，温度就会升高 $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 君住所的温度。
样例输入 复制
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 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)$。