AOJ 0636 フェーン現象(Foehn Phenomena)

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0636&lang=jp

解法

B[i] = A[i] - A[i + 1] という数列 B[i] を考えるのが良いです．
すると，A[l] から A[r] の変化が x だとすると，B[l - 1] と B[r] にしか影響を及ぼさないことがわかります．その他の場所は影響が相殺されるからです．
あとは変化によって B[l - 1]，B[r] の値が正になるのか負になるのかを見てやると，あとは総和を求めるだけになるので，BITなどで管理すると頭を使わなくて楽です．

ソースコード

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

using ll = long long;
constexpr ll M = 1e9 + 7;

// 0-indexed
template <typename T>
class fenwick_tree {
public:
    fenwick_tree(int n) : n(n), dat(n, 0) {}

    void add(int i, T value) {
        for(; i<n; i |= i + 1) {
            dat[i] += value;
        }
    }

    // [0, i)
    T sum(int i) const {
        T res = 0;
        for(; i>=0; i = (i & (i+1)) - 1) {
            res += dat[i];
        }
        return res;
    }
    // [l, r)
    T sum(int l, int r) const {
        return sum(r-1) - sum(l-1);
    }

    T get(int i) const {
        return sum(i) - sum(i - 1);
    }

private:
    const int n;
    std::vector<T> dat;
};


int main() {
    ll N, Q, S, T;
    cin >> N >> Q >> S >> T;
    vector<ll> A(N + 1);
    for(int i = 0; i <= N; ++i) {
        cin >> A[i];
    }

    fenwick_tree<ll> bit(N);
    for(int i = 0; i < N; ++i) {
        if(A[i] < A[i + 1]) {
            bit.add(i, (A[i] - A[i + 1]) * S);
        } else {
            bit.add(i, (A[i] - A[i + 1]) * T);
        }
    }

    while(Q--) {
        int l, r, x;
        cin >> l >> r >> x;
        ll L = bit.get(l - 1), R = bit.get(r);
        ll new_L = L / (L < 0 ? S : T) - x;
        ll new_R = R / (R < 0 ? S : T) + x;
        bit.add(l - 1, -L + new_L * (new_L < 0 ? S : T));
        bit.add(r, -R + new_R * (new_R < 0 ? S : T));
        cout << bit.sum(0, N) << endl;
    }
}

感想

差をもった数列を扱う問題を最近解いたのですぐわかった．
こういう処理は典型らしい．
べつにBITは使わなくていいです．総和を持っておいて逐一変えるだけでOK．