列全体から計算される値を部分的な要素の更新の度に計算する実装パターン

こどふぉ頻出です．大体やるだけなんだけどバグらせないようにしたいという記事です

次の問題を考えます
http://codeforces.com/contest/1467/problem/B
概要: 数列 $a$ が与えられるので「 $a_{i -1} < a_i > a_{i + 1}$ または $a_{i - 1} > a_i < a_{i + 1}$ 」が成り立つ $i$ の個数を考えたときに，高々一回好きな位置の値を好きな値に変えれるのでその個数を最小化してください

少し考えるとある値を変更する場合はその隣り合う数のどちらかと同じ値に変更してしまうことにしてよいことがわかります．また，変更によって影響が及ぶのは変更した値とその隣り合う二つの数だけなので変更なしの計算結果との差分をとればいいです

実装では次の二つを用意します
A. ある位置を受け取って条件をそのまま記述してその結果を返します．このとき区間範囲外の位置も受け付けて適切な値を返すようにしておくと残りの実装をより脳死でできるのでそのようにする
B. ある区間を受け取ってその区間の各位置について A を計算してその結果を返す

これを使って次のようなことをします
C. まず変更なしの計算は区間全体を B に渡せばよくて，これを val とします．次に各変更について考えます．ある位置の変更に対してその影響が及ぶ区間をとって変更前の状態でその区間を B に渡してその結果を val から引きます．そのあと変更後の状態で同じ区間を B に渡してその結果を val に足します．これが変更後の結果になります

これの嬉しさは変更の位置や種類等に関心を持つ必要がない点です

具体的な実装は次のようにしました
A

int calc_at_point(const vector<int> &a, int idx) {
        int n = a.size();
        if (idx > 0 && idx < n - 1) {
                if (a[idx - 1] > a[idx] && a[idx] < a[idx + 1]) {
                        return 1;
                }
                if (a[idx - 1] < a[idx] && a[idx] > a[idx + 1]) {
                        return 1;
                }
        }
        return 0;
};

B

int calc_at_range(const vector<int> &a, int l, int r) {
        int res = 0;
        for (int i = l; i <= r; i ++) {
                res += calc_at_point(a, i);
        }
        return res;
}

C

int val = calc_at_range(a, 0, n - 1);
int ans = val;
rep(i, n) {
        int o = a[i];
        for (int d = -1; d <= 1; d += 2) {
                if (0 <= i + d && i + d < n) {
                        int t = val;
                        t -= calc_at_range(a, i - 1, i + 1);
                        a[i] = a[i + d];
                        t += calc_at_range(a, i - 1, i + 1);
                        a[i] = o;
                        ans = min(ans, t);
                }
        }
}
cout << ans << '\n';

似たような問題をもう一つ考えます
http://codeforces.com/contest/1420/problem/c2
概要: 数列 $a$ が与えられるので，そこから好きな部分列をとってそれを $b$ としたときに $b_0 - b_1 + b_2 - b_3 + ... $ の値が最大になるようにしてください．ただしある $l, r$ について $a_l$ と $a_r$ を swap してくださいというクエリを順に処理しながらその都度最大値を求めてください

行列をデータ構造にのせて解くこともできると思いますが，ここでは別の解き方をします．まずよく考えると実は + として使う数というのは必ず $a_{i - 1} < a_i > a_{i + 1}$ を満たす $a_i$ であるということが言えます．証明としては，仮に $a_{i - 1} \geq a_i$ なときに $a_i$ を + として使うのだとすると $a_{i - 1}$ は使わないか - として使うかのどちらかになりますが， もし使わないなら $a_i$ ではなく $a_{i - 1}$ を + として使った方が損することはないです．もし - として使うなら， $a_i$ も $a_{i - 1}$ もどちらも使わないとする方が損することはないです．よってこのような構造はないと思って良いことがわかってこれは右側についても言えるので，言えました．同様にして - として使う数は必ず $a_{i - 1} > a_i < a_{i + 1}$ を満たす $a_i$ であることも言えて，逆に以上の条件を満たすものは全部 +/- として使って損はしないので，そのようなものの総和をとる問題になりました

最初の問題とほとんど同じように次のような実装ができます（ただし l と r の距離が近い場合は独立に計算しようとすると差分が二回計算されたりして壊れるのでまとめて一つの区間で計算しています）
A

int calc_at_point(const vector<int> &a, int idx) {
        int n = a.size();
        if (idx < 0 || n <= idx) {
                return 0;
        }
        bool add = true, sub = true;
        if (idx == 0 || idx == n - 1) {
                sub = false;
        }
        if (idx > 0) {
                add = add && a[idx - 1] < a[idx];
                sub = sub && a[idx - 1] > a[idx];
        }
        if (idx < n - 1) {
                add = add && a[idx + 1] < a[idx];
                sub = sub && a[idx + 1] > a[idx];
        }
        if (add) {
                return a[idx];
        } else if (sub) {
                return -a[idx];
        } else {
                return 0;
        }
}

B

ll calc_at_range(const vector<int> &a, int l, int r) {
        ll res = 0;
        for (int i = l; i <= r; i ++) {
                res += calc_at_point(a, i);
        }
        return res;
}

C

ll ans = calc_at_range(a, 0, n - 1);
cout << ans << '\n';
while (q --) {
        int l, r;
        cin >> l >> r;
        l --, r --;
        if (r - l >= 5) {
                ans -= calc_at_range(a, l - 1, l + 1);
                ans -= calc_at_range(a, r - 1, r + 1);
                swap(a[l], a[r]);
                ans += calc_at_range(a, l - 1, l + 1);
                ans += calc_at_range(a, r - 1, r + 1);
        } else {
                ans -= calc_at_range(a, l - 1, r + 1);
                swap(a[l], a[r]);
                ans += calc_at_range(a, l - 1, r + 1);
        }
        cout << ans << '\n';
}