この解説は、永続データ構造を使わずに、ビルの追加時に求めた各長さでの答えを配列に持たせて解く解法です。公式解説と同様に「右端から \(k\) 個を削って置き換える」操作を行いますが、削った後の状態を保持しないため、操作 2 のためのロールバックが不要になります。

準備

\(M\) 個のビルが存在するとき、列 \(C_1, C_2, \ldots, C_M\) に対する最適解はすべての\(i\)について\(B_i = \min_{j}\left(C_j + D|i-j|\right)\) です。

ここで、左からの制約だけを考えた値

• \(L_1 = C_1,\quad L_i = \min(C_i,\ L_{i-1} + D)\)

と、長さ \(i\) のプレフィックス \(C_1, \ldots, C_i\) に対する答え \(\text{ans}_i\) を定義します（\(\text{ans}_0 = 0\)）。

\(L_i\) と \(\text{ans}_i\) はいずれも \(C_1, \ldots, C_i\) だけで決まる値であり、\(i\) 番目のビルが列に残っている間は右端で追加・削除が行われても変化しません。\(\text{ans}_i\) は「長さが \(i\) のときに操作 3 で答える値」そのものなので、\(i\) 番目のビルを追加した時点で計算した答えを配列に保持しておくだけでよく、削除で \(i\) 番目のビルが消えるまで再計算は不要です。

追加操作の遷移

長さ \(M-1\) の列（末尾の左制約は \(L_{M-1}\)）に高さ \(x\) のビルを追加するとします。

\(x + D \ge L_{M-1}\) のときは、既存のビルを低くする必要がありません。

• \(\text{ans}_M = \text{ans}_{M-1} + \min(x,\ L_{M-1} + D)\)

\(x + D < L_{M-1}\) のときは、\(B_{M-1} = x + D,\ B_M = x\) となり、さらに左のビルへの影響は「高さ \(x+D\) のビルを位置 \(M-1\) に置いた」場合と一致します。すなわち

• \(\text{ans}(C_1, \ldots, C_{M-1}, x) = \text{ans}(C_1, \ldots, C_{M-2}, x + D) + x\)

が成り立ちます。このとき、さらに \(x + 2D < L_{M-2}\) であれば

• \(\text{ans}(C_1, \ldots, C_{M-2}, x + D) + x = \text{ans}(C_1, \ldots, C_{M-3}, x + 2D) + (x + D) + x\)

と置き換えられます。

この置き換えを \(k\) 回繰り返して位置 \(i = M-1-k\) で止まる、つまり \(x + (k+1)D \ge L_i\) となる場合、答えは

• \(\text{ans}_M = \text{ans}_i + \min\left(x + kD,\ L_i + D\right) + \sum_{j=0}^{k-1}(x + jD)\)

と書けます。ただし \(i = 0\)（全部置き換え）のときは \(L_0\) は定義されないため第 2 項を \(x + kD\) とします。

止まる位置の求め方

止まる位置は、\(L_i \le x + (M-i)D\)、すなわち

• \(L_i + iD \le x + MD\)

を満たす最大の \(i\) です。そこで、\(L_i + iD\) を位置 \(i\) に載せた min セグメント木を用意して、「\([1, M)\) のうち \(L_i + iD \le x + MD\) を満たす最も右の \(i\)」をセグメント木上の二分探索で求めます。

操作 2 は列の長さを縮める（ \(M\) を \(1\) 減らす）だけです。操作 3 は \(\text{ans}_M\) を出力します。

時間計算量は \(O(Q \log Q)\) です。

なお、置き換えを続けている間は \(x + jD < L_i \le 10^9\) なので、上の式は 64 bit 整数の範囲に収まります。

実装例(C++):

#include <bits/stdc++.h>
#include <atcoder/segtree>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;

ll op(ll a, ll b) { return min(a, b); }
ll e() { return INF; }

int main() {
    int Q; ll D;
    cin >> Q >> D;

    atcoder::segtree<ll, op, e> seg(Q + 2); // seg[i] = L_i + i*D
    seg.set(0, -1); // 番兵
    vector<ll> L(Q + 2), ans(Q + 2);
    int M = 0;

    while (Q--) {
        int t; cin >> t;
        if (t == 1) {
            ll x; cin >> x;
            M++;
            const ll T = x + M * D;
            const int i = seg.min_left(M, [&](ll v) { return v > T; }) - 1;
            const ll k = M - 1 - i;
            const ll cur = (i == 0) ? x + k * D : min(x + k * D, L[i] + D);
            ans[M] = ans[i] + cur + k * x + D * k * (k - 1) / 2;
            L[M] = (M == 1) ? x : min(x, L[M - 1] + D);
            seg.set(M, L[M] + M * D);
        }
        else if (t == 2) {
            M--;
        }
        else {
            cout << ans[M] << "\n";
        }
    }
}