[AdditionalFile2332.zip](file://AdditionalFile2332.zip?type=additional_file)

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

输入输出样例 #1

输入 #1

3 5 1 2
0
4
1
8
1 2 2
1 1 -2
2 3 5
1 2 -1
1 3 5

输出 #1

-5
-7
-13
-13
-18

输入输出样例 #2

输入 #2

2 2 5 5
0
6
-1
1 1 4
1 2 8

输出 #2

5
-35

输入输出样例 #3

输入 #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

说明/提示

【数据范围与约定】

对于所有数据，均满足：

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

#2332. 「JOI 2017 Final」焚风现象

标签: 传统 | 时间限制: 200 ms | 内存限制: 256 MiB |

题目描述

题目译自 JOI 2017 Final T1「フェーン現象 / Foehn Phenomena」

焚风是是由于空气作绝热下沉运动时，因温度升高湿度降低而形成的一种干热风。焚风常出现在山脉背风坡，由山地引发的过山气流在背风坡下沉，使过山气流变得干热的一种风。在高压区，空气下沉也可产生焚风。

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$ 米，温度就会下降 $S$ 度；
• 如果 $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 君住所的温度。

样例 1

输入

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

最初，地点 $0,1,2,3$ 的海拔分别是 $0,4,1,8$。第一天地壳运动后，海拔分别为 $0,6,3,8$。 此时，风的温度分别为 $0,-6,0,-5$。

样例 2

输入

2 2 5 5
0
6
-1
1 1 4
1 2 8

输出

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

输出

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)$。