#P11790. [JOI 2017 Final] 焚风现象 / Foehn Phenomena

[JOI 2017 Final] 焚风现象 / Foehn Phenomena

题目描述

你知道 N+1N+1 个地点的海拔 AiA_i,编号为 0N0 \dots N,有风从 00 吹向 NN,想让你求出地点 NN 的风的温度,保证 A0=0A_0=0

规则:

  • 如果 Ai=Ai+1A_i=A_{i+1},风的温度不变。
  • 如果 Ai>Ai+1A_i>A_{i+1},由于海拔降低,风的温度会上升 (AiAi+1)×T(A_i-A_{i+1})\times T 度。
  • 如果 Ai<Ai+1A_i<A_{i+1},由于海拔升高,风的温度会下降 (Ai+1Ai)×S(A_{i+1}-A_i)\times S 度。

输入格式

  • 第一行输入包括四个被空格隔开的整数 N,Q,S,TN,Q,S,T。这表示 JOI 先生在地点 NN 有一所房子,有 QQ 次地壳运动,海拔每上升 11 米的话,风的温度会降低 SS 度,海拔每下降一米的话,风的温度会上升 TT 度。

  • 接下来的 N+1N+1 行中第 ii(1iN+1)(1\leq i\leq N+1) 包含一个整数 Ai1A_{i-1},表示地壳运动前地点 i1i-1 的海拔高度。

  • 接下来的 QQ 行中第 jj(1jQ)(1\leq j\leq Q) 包括三个被空格隔开的整数 Lj,Rj,XjL_j,R_j,X_j,这表示第 jj 天地壳运动使地点 LjL_j 到地点 RjR_j 中这些地点的海拔变化了 XjX_j

输出格式

输出 QQ 行,第 jj 行的输出代表第 jj 天地壳运动后 JOI 先生家的风的温度。 (即 NN 位置的风的温度。)

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

提示

【数据范围与约定】

对于所有数据,均满足:

  • 1N2000001\le N\le 200000
  • 1Q2000001\le Q\le 200000
  • 1S10000001\le S\le 1000000
  • 1T10000001\le T\le 1000000
  • 1000000Ai1000000(1iN)-1000000\le A_i\le 1000000(1\le i\le N)
  • 1LjRjN(1jQ)1\le L_j\le R_j\le N ( 1\le j\le Q)
  • 1000000Xj1000000(1jQ)−1000000\le Xj\le 1000000 (1\le j\le Q)
  1. Subtask 113030 pts):满足 N,Q2000N,Q \le 2000
  2. Subtask 111010 pts):满足 S=TS=T
  3. Subtask 116060 pts):无特殊限制。