题解：P11790 [JOI 2017 Final] 焚风现象 / Foehn Phenomena

· · 题解

读完题，我们首先关注的是相邻地点的高度差。可以通过差分数组来表示相邻地点的高度差，即 b[i] = a[i] - a[i + 1]。然后，温度变化的贡献来自于这些高度差的变化。温度变化取决于高度差的正负，正值时温度上升，负值时温度下降。

每次操作会影响区间 [L, R] 内的某些高度差，这些变化会影响温度的变化。我们只需要关心操作影响的区间两端的相邻高度差，从而计算它们的温度变化。

现在考虑具体实现：

  1. 首先计算每对相邻地点的海拔差，并根据题目规则计算初始的温度总和。
  2. 然后，通过差分数组来维护相邻地点的海拔差，只更新受影响的边界。
  3. 每次操作时，只需要更新左右边界的相邻高度差，从而动态更新温度总和。

Code

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); 

    int N, Q, S, T;
    cin >> N >> Q >> S >> T;

    vector<long long> A(N + 1);
    for (int i = 0; i <= N; ++i) {
        cin >> A[i];
    }

    vector<long long> dif(N);
    long long sum = 0;

    // 初始化差分数组 dif 和温度总和 sum
    for (int i = 0; i < N; ++i) {
        dif[i] = A[i] - A[i + 1];
        sum += dif[i] > 0 ? dif[i] * T : dif[i] * S;
    }

    // 处理每次查询
    for (int q = 0; q < Q; ++q) {
        int L, R, X;
        cin >> L >> R >> X;

        // 更新 L 左边的差分
        if (L >= 1) {
            int i = L - 1;
            long long old = dif[i];
            sum -= old > 0 ? old * T : old * S;
            dif[i] -= X;
            long long now = dif[i];
            sum += now > 0 ? now * T : now * S;
        }

        // 更新 R 右边的差分
        if (R < N) {
            int i = R;
            long long old = dif[i]; 
            sum -= old > 0 ? old * T : old * S;
            dif[i] += X;
            long long now = dif[i];
            sum += now > 0 ? now * T : now * S;
        }

        // 输出当前温度总和
        cout << sum << '\n';
    }

    return 0;
}