P11790 [JOI 2017 Final] 焚风现象 / 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$ 位置的风的温度。）

【数据范围与约定】 对于所有数据，均满足： - $1\le N\le 200000$。 - $1\le Q\le 200000$。 - $1\le S\le 1000000$。 - $1\le T\le 1000000$。 - $-1000000\le A_i\le 1000000(1\le i\le N)$． - $1\le L_j\le R_j\le N ( 1\le j\le Q)$。 - $−1000000\le Xj\le 1000000 (1\le j\le Q)$。 1. Subtask $1$（$30$ pts）：满足 $N,Q \le 2000$。 2. Subtask $1$（$10$ pts）：满足 $S=T$。 3. Subtask $1$（$60$ pts）：无特殊限制。