Description:

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

IOI 王国永远刮着海风。风从地点 0 0 0 依次吹到地点 1 1 1，地点 2 2 2 ……直到地点 N N N，共 N + 1 N+1 N+1 个地点。JOI 君住在地点 N N N。地点 0 0 0 的海拔 A 0 = 0 A_0=0 A0​=0，地点 i ( 1 ⩽ i ⩽ N ) i(1\leqslant i\leqslant N) i(1⩽i⩽N) 的海拔为 A i A_i Ai​。
地表风的温度随海拔升降而变化。地点 0 0 0 在海边，温度为 0 0 0 度；对于任一地点 i ( 0 ⩽ i &lt; N ) i(0\leqslant i&lt;N) i(0⩽i<N)，从地点 i i i 吹到地点 i + 1 i+1 i+1 的风的温差仅取决于两地的海拔差。具体来说：

  • 如果 A i = A i + 1 A_i=A_{i+1} Ai​=Ai+1​，风的温度不变；
  • 如果 A i &lt; A i + 1 A_i&lt;A_{i+1} Ai​<Ai+1​，风每爬升 1 1 1 米，温度就会下降 S S S 度；
  • 如果 A i &gt; A i + 1 A_i&gt; A_{i+1} Ai​>Ai+1​，风每下沉 1 1 1 米，温度就会升高 T T T 度。

IOI 国的地壳运动很强烈。你得到了 Q Q Q 天来地壳运动的数据。在第 j j j 日 ( 1 ⩽ j ⩽ Q ) (1\leqslant j\leqslant Q) (1⩽j⩽Q)，地点 L j , L j + 1 , … , R j ( 1 ⩽ L j ⩽ R j ⩽ N ) L_j, L_j+1, \ldots, R_j (1\leqslant L_j\leqslant R_j\leqslant N) Lj​,Lj​+1,…,Rj​(1⩽Lj​⩽Rj​⩽N) 的海拔升高了 X j X_j Xj​，注意 X j X_j Xj​ 可能是负数。
你的任务是，计算每天地壳运动后 JOI 君住所的温度。

Input:

第一行有四个整数 N , Q , S , T N, Q, S, T N,Q,S,T 用空格分隔。
在接下来的 N + 1 N+1 N+1 行中，第 i i i 行 ( 1 ⩽ i ⩽ N + 1 ) (1\leqslant i\leqslant N+1) (1⩽i⩽N+1) 有一个整数 A i − 1 A_{i-1} Ai−1​。
在接下来的 Q Q Q 行中，第 j j j 行 ( 1 ⩽ j ⩽ Q ) (1\leqslant j\leqslant Q) (1⩽j⩽Q) 有三个整数 L j , R j , X j L_j, R_j, X_j Lj​,Rj​,Xj​ 用空格分隔。
输入的所有数的含义见题目描述。

对于 30 % 30\% 30% 的数据， N , Q ⩽ 2000 N, Q\leqslant 2000 N,Q⩽2000；
对于另外 10 % 10\% 10% 的数据， S = T S=T S=T；
对于所有数据， 1 ⩽ N , Q ⩽ 2 × 1 0 5 , 1 ⩽ S , T ⩽ 1 0 6 ; 1\leqslant N, Q\leqslant 2\times 10^5, 1\leqslant S, T\leqslant 10^6; 1⩽N,Q⩽2×105,1⩽S,T⩽106; A 0 = 0 , ∣ A i ∣ ⩽ 1 0 6 ( 1 ⩽ i ⩽ N ) ; A_0=0, |A_i|\leqslant 10^6(1\leqslant i\leqslant N); A0​=0,∣Ai​∣⩽106(1⩽i⩽N); 1 ⩽ L j ⩽ R j ⩽ N , 1\leqslant L_j\leqslant R_j\leqslant N, 1⩽Lj​⩽Rj​⩽N, ∣ X j ∣ ⩽ 1 0 6 |X_j|\leqslant 10^6 ∣Xj​∣⩽106 ( 1 ⩽ j ⩽ Q ) (1\leqslant j\leqslant Q) (1⩽j⩽Q)。

Output:

共 Q Q Q 行，第 j j j 行 ( 1 ⩽ j ⩽ Q ) (1\leqslant j\leqslant Q) (1⩽j⩽Q) 有一个整数，表示第 j j j 日地壳运动后 JOI 君住所的温度。

Sample Input:

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

Sample Output:

-5
-7
-13
-13
-18

Hint:

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

Sample Input:

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

Sample Output:

5
-35

Sample Input:

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

Sample Output:

277
277
322
290
290
290
290
370

题目链接

这道题目和洛谷 AT2442 フェーン現象 (Foehn Phenomena)一样，洛谷在翻译上有一个S和T写反了，导致我一直WA……

题目很简单，N个点的海拔会变化，温度随点与前一点海拔差的变化而变化，问Q此区间海拔变化之后N点的温度。

因为温度只与海拔差相关，所以可以用差分数组记录，差分数组在进行区间修改时非常方便。

而进行Q次区间修改之前可以先计算出初始N点的温度，之后每次修改时先减去左右边界之前海拔差的温度，再加上更新后海拔差的温度。

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

long long N, Q, S, T;
long long Ans;
long long A[maxn];

long long Get(long long X) {
  return X > 0 ? -(X * S) : ((-X) * T);
}

int main(int argc, char *argv[]) {
  scanf("%lld%lld%lld%lld", &N, &Q, &S, &T);
  Ans = 0;
  for (long long i = 0, Last = 0, X; i <= N; ++i) {
    scanf("%lld", &X);
    A[i] = X - Last;
    Last = X;
    Ans += Get(A[i]);
  }
  for (long long i = 1, L, R, X; i <= Q; ++i) {
    scanf("%lld%lld%lld", &L, &R, &X);
    Ans -= Get(A[L]);
    A[L] += X;
    Ans += Get(A[L]);
    if (R != N) {
      Ans -= Get(A[R + 1]);
      A[R + 1] -= X;
      Ans += Get(A[R + 1]);
    }
    printf("%lld\n", Ans);
  }
  return 0;
}