差分だけ更新していく系の問題！！！

類題集 (めちゃむずいのもある)

問題概要

正の整数 $S, T$ が与えられる。長さ $N+1$ の数列 $A_{0}, A_{1}, \dots, A_{N}$ のスコアが次のように定まる。

各に対して以下の値を合算する
- $A_{i} \lt A_{i+1}$ のとき： $-S(A_{i+1} - A_{i})$
- $A_{i} \ge A_{i+1}$ のとき： $-T(A_{i+1} - A_{i})$

$A_{0} = 0$ を満たすような初期数列 $A_{0}, A_{1}, \dots, A_{N}$ が与えられる。以下の $Q$ 個のクエリに答えよ。

各クエリは 3 つの整数 $L, R, X$ が与えられる
$A_{L}, A_{L+1}, \dots, A_{R}$ に $X$ を加算する
加算後の数列 $A$ のスコアを出力せよ

制約

$1 \le N, Q \le 2 \times 10^{5}$

考えたこと

各クエリは、区間 $\lbrack L, R \rbrack$ に値 $X$ を加算する操作だと言える。このように「区間に値を加算する」という操作を見ると、いもす法を連想する人も多いと思う。

実際今回の問題も、いもす法の類推が役に立つ。つまり、数列 $A$ の階差数列を考えるのだ。

$D_{i} = A_{i+1} - A_{i}$

とする。 $D$ は長さ $N$ の数列となる。このとき、操作は次のように言い換えられる。

$D_{L-1}$ += $X$ とする
$D_{R}$ -= $X$ とする

つまり、「区間に対する加算」が「2 点に対する加算」へと置き換わるのだ！！！こうすれば、各クエリを高速に処理できるようになる。

数列のスコアを差分更新していく

さらに言えば、数列のスコアも $D$ を用いると簡潔に表せる。まず初期状態のスコアは愚直に $O(N)$ で計算していくことにしよう。

その後のクエリは、数列 $D$ の 2 点のみが更新されるので、更新によるスコアの差分は 2 点分の変更のみ反映させれば OK。よって

最初のスコア計算 $O(N)$
その後のクエリ処理 $O(Q)$

となって、全体の計算量は $O(N+Q)$ となる。

コード

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

int main() {
    long long N, Q, S, T;
    cin >> N >> Q >> S >> T;
    vector<long long> A(N+1, 0), D(N);
    cin >> A[0];
    for (int i = 1; i <= N; ++i) cin >> A[i], D[i-1] = A[i] - A[i-1];
    
    auto cost = [&](int i) -> long long {
        if (i >= N) return 0;
        if (D[i] > 0) return -D[i] * S;
        else return -D[i] * T;
    };
    
    long long res = 0;
    for (int i = 0; i < N; ++i) res += cost(i);
    for (int q = 0; q < Q; ++q) {
        long long L, R, X;
        cin >> L >> R >> X;
        long long before = cost(L-1) + cost(R);
        D[L-1] += X;
        if (R < N) D[R] -= X;
        long long after = cost(L-1) + cost(R);
        res += after - before;
        cout << res << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 本選 2017 A - フェーン現象 (AOJ 0636, 難易度 6)

問題概要

制約

考えたこと

数列のスコアを差分更新していく

コード