LibreOJ #2332. 「JOI 2017 Final」焚风现象(差分数组)

Description:

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

IOI 王国永远刮着海风。风从地点 $0$ 依次吹到地点 $1$ ，地点 $2$ ……直到地点 $N$ ，共 $N + 1$ 个地点。JOI 君住在地点 $N$ 。地点 $0$ 的海拔 $A_{0} = 0$ ，地点 $i (1 ⩽ i ⩽ N)$ 的海拔为 $A_{i}$ 。
地表风的温度随海拔升降而变化。地点 $0$ 在海边，温度为 $0$ 度；对于任一地点 $i (0 ⩽ i < N)$ ，从地点 $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$ 日 $(1 ⩽ j ⩽ Q)$ ，地点 $L_{j}, L_{j} + 1, \dots, R_{j} (1 ⩽ L_{j} ⩽ R_{j} ⩽ N)$ 的海拔升高了 $X_{j}$ ，注意 $X_{j}$ 可能是负数。
你的任务是，计算每天地壳运动后 JOI 君住所的温度。

Input:

第一行有四个整数 $N, Q, S, T$ 用空格分隔。
在接下来的 $N + 1$ 行中，第 $i$ 行 $(1 ⩽ i ⩽ N + 1)$ 有一个整数 $A_{i - 1}$ 。
在接下来的 $Q$ 行中，第 $j$ 行 $(1 ⩽ j ⩽ Q)$ 有三个整数 $L_{j}, R_{j}, X_{j}$ 用空格分隔。
输入的所有数的含义见题目描述。

对于 $30 %$ 的数据， $N, Q ⩽ 2000$ ；
对于另外 $10 %$ 的数据， $S = T$ ；
对于所有数据， $1 ⩽ N, Q ⩽ 2 \times 1 0^{5}, 1 ⩽ S, T ⩽ 1 0^{6};$ $A_{0} = 0, ∣ A_{i} ∣ ⩽ 1 0^{6} (1 ⩽ i ⩽ N);$ $1 ⩽ L_{j} ⩽ R_{j} ⩽ N,$ $∣ X_{j} ∣ ⩽ 1 0^{6}$ $(1 ⩽ j ⩽ Q)$ 。

Output:

共 $Q$ 行，第 $j$ 行 $(1 ⩽ j ⩽ Q)$ 有一个整数，表示第 $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, 4, 1, 8$ 。第一天地壳运动后，海拔分别为 $0, 6, 3, 8$ 。此时，风的温度分别为 $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;
}