P11790 [JOI 2017 Final] 焚风现象 题解

· · 题解

发现做法唐了，回来重新思考。

如果没有修改操作，我们可以直接 O(n) 算出答案，于是我们考虑每次操作会改变什么。

其实影响最终温度的只有相邻两地的相对海拔差，每次给一个区间的海拔加减，这个区间内的相对海拔差是不会变的，只有区间左右两边相邻的海拔差会改变，考虑使用差分数组维护，每次动态更新答案即可。

时间复杂度：O(n + q)，注意本题要开 long long。

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int ll

const int N = 1000000 + 10;
const int inf = 1e9 + 7;
using namespace std;

inline int read () {
    int x = 0, k = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') k = -1; c = getchar(); }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return (1ll * x * k);
}

int n, q, s, t, ret;
int a[N], b[N]; 

int calc (int x) {
    if (x > 0) return x * t;
    else return x * s;
}

signed main() {
    n = read(), q = read(), s = read(), t = read();
    for (int i = 0; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = a[i - 1] - a[i], ret += calc(b[i]);
    for (int i = 1; i <= q; ++i) {
        int l = read(), r = read(), x = read();
        ret -= calc(b[l]), ret -= (r < n) * calc(b[r + 1]);
        b[l] -= x, b[r + 1] += x;
        ret += calc(b[l]), ret += (r < n) * calc(b[r + 1]);
        cout << ret << endl;
    }
    return 0;
}