题目描述
你知道 N+1 个地点的海拔 Ai,编号为 0…N,有风从 0 吹向 N,想让你求出地点 N 的风的温度,保证 A0=0。
规则:
- 如果 Ai=Ai+1,风的温度不变。
- 如果 Ai>Ai+1,由于海拔降低,风的温度会上升 (Ai−Ai+1)×T 度。
- 如果 Ai<Ai+1,由于海拔升高,风的温度会下降 (Ai+1−Ai)×S 度。
输入格式
-
第一行输入包括四个被空格隔开的整数 N,Q,S,T。这表示 JOI 先生在地点 N 有一所房子,有 Q 次地壳运动,海拔每上升 1 米的话,风的温度会降低 S 度,海拔每下降一米的话,风的温度会上升 T 度。
-
接下来的 N+1 行中第 i 行 (1≤i≤N+1) 包含一个整数 Ai−1,表示地壳运动前地点 i−1 的海拔高度。
-
接下来的 Q 行中第 j 行 (1≤j≤Q) 包括三个被空格隔开的整数 Lj,Rj,Xj,这表示第 j 天地壳运动使地点 Lj 到地点 Rj 中这些地点的海拔变化了 Xj。
输出格式
输出 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≤N≤200000。
- 1≤Q≤200000。
- 1≤S≤1000000。
- 1≤T≤1000000。
- −1000000≤Ai≤1000000(1≤i≤N).
- 1≤Lj≤Rj≤N(1≤j≤Q)。
- −1000000≤Xj≤1000000(1≤j≤Q)。
- Subtask 1(30 pts):满足 N,Q≤2000。
- Subtask 1(10 pts):满足 S=T。
- Subtask 1(60 pts):无特殊限制。