You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你知道 $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$ 位置的风的温度。）

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

提示

【数据范围与约定】

对于所有数据，均满足：

• $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）：无特殊限制。