概要

ビルを右端に追加・削除しながら、各時点で「高さを下げることだけを許したとき、隣接差が \(D\) 以下になるような高さの合計最大値」を求めます。

重要なのは、高さをそのまま扱うのではなく、位置 \(i\) に対して \(D i\) を足した値に変換すると、追加時の更新が「ある値より大きいものをまとめて下げる」という操作になることです。

考察

現在のビル数を \(M\)、元の高さを \(C_i\)、調整後の高さを \(B_i\) とします。

条件は次の通りです。

\[ 0 \leq B_i \leq C_i \]

\[ |B_i - B_{i+1}| \leq D \]

このまま扱うと、ビルを追加するたびに全体の最適な高さが変わる可能性があります。
毎回全ビルについて最適値を計算すると、最悪で \(O(Q^2)\) になり、\(Q \leq 10^5\) では間に合いません。

そこで、次の変換を考えます。

\[ A_i = B_i + D i \]

また、元の高さの上限も変換して

\[ T_i = C_i + D i \]

とします。

すると、\(B_i \leq C_i\) は

\[ A_i \leq T_i \]

になります。

さらに隣接条件を変形すると、

\[ B_i \leq B_{i+1} + D \]

は

\[ A_i \leq A_{i+1} \]

となり、

\[ B_{i+1} \leq B_i + D \]

は

\[ A_{i+1} \leq A_i + 2D \]

となります。

つまり、変換後の \(A_i\) は次を満たす必要があります。

• \(A_i \leq T_i\)
• \(A_i \leq A_{i+1}\)
• \(A_{i+1} \leq A_i + 2D\)

また、求めたい値は

\[ \sum_{i=1}^{M} B_i = \sum_{i=1}^{M} A_i - D \sum_{i=1}^{M} i \]

なので、

\[ \sum A_i - D \frac{M(M+1)}{2} \]

を出力すればよいです。

---

ここで、現在の最適な \(A_1, A_2, \dots, A_n\) が分かっているとします。
新しく右端にビルを追加し、その変換後の上限を

\[ T = C_{n+1} + D(n+1) \]

とします。

新しい最適値は次のように更新できます。

• 既存の値はすべて \(\min(A_i, T)\) になる
• 新しい末尾の値は \(\min(T, A_n + 2D)\) になる

つまり、

\[ A_i' = \min(A_i, T) \quad (1 \leq i \leq n) \]

\[ A_{n+1}' = \min(T, A_n + 2D) \]

です。

なぜなら、新しい列では単調性 \(A_i \leq A_{i+1}\) があるため、すべての既存の値も新しい末尾以下、つまり \(T\) 以下でなければなりません。
そのため、\(T\) より大きい既存の値はすべて \(T\) まで下げる必要があります。

また、新しい末尾は直前との差の条件から

\[ A_{n+1} \leq A_n + 2D \]

も満たす必要があります。

したがって、追加操作は本質的に次の操作になります。

1. 現在の \(A_i\) のうち、\(T\) より大きいものをすべて \(T\) に変更する
2. 新しい値 \(U = \min(T, A_n + 2D)\) を追加する

これが重要な観察です。

アルゴリズム

現在の最適な \(A_i\) たちを多重集合として管理します。
必要なのは順序そのものではなく、

• \(T\) より大きい値が何個あるか
• それらを削除する
• その個数分だけ \(T\) を追加する
• 新しい末尾値 \(U\) を追加する
• 現在の \(\sum A_i\) を求める

という操作です。

これを高速に行うために、座標圧縮した値の上に永続セグメント木を作ります。

追加操作

現在のビル数を \(n\) とし、新しいビルの高さを \(x\) とします。

新しい位置は \(n+1\) なので、

\[ T = x + D(n+1) \]

です。

また、現在の末尾の最適値を \(last\) とすると、新しく追加される末尾値は

\[ U = \min(T, last + 2D) \]

です。

ただし、空の列に追加する場合は

\[ U = T \]

です。

セグメント木上では次を行います。

1. \(T\) より大きい値の個数を数える
2. \(T\) より大きい値をすべて削除する
3. 削除した個数分だけ \(T\) を追加する
4. \(U\) を 1 個追加する

コードでは、\(T = U\) の場合はまとめて \(T\) に追加しています。

削除操作

ビルは常に右端から削除されます。
つまり操作全体はスタックのように扱えます。

そこで、各時点のセグメント木の root をスタックに積んでおきます。

• 追加操作では、新しい root を作って stack に push
• 削除操作では、root stack を pop

永続セグメント木を使うことで、過去の状態を壊さずに新しい状態を作れます。

質問操作

現在の root に保存されている \(\sum A_i\) を S とします。
現在のビル数を \(M\) とすると、答えは

\[ S - D \frac{M(M+1)}{2} \]

です。

計算量

• 時間計算量: \(O(Q \log Q)\)
• 空間計算量: \(O(Q \log Q)\)

各追加操作で、永続セグメント木に対する更新やクエリを \(O(\log Q)\) で行います。
削除操作と質問操作はほぼ \(O(1)\) です。

実装のポイント

• 値 \(T\) や \(U\) は最大で \(10^{14}\) 程度になるため、long long が必要です。

• \(\sum A_i\) や計算途中の積は大きくなる可能性があるため、コードでは安全に __int128 を使っています。

• 座標圧縮のために、最初にすべてのクエリを読み込み、追加操作ごとの \(T, U\) を事前に計算しています。

• 削除操作による巻き戻しのために、通常のセグメント木ではなく永続セグメント木を使います。

• 現在のビル数は、root のスタックサイズから求められます。具体的には root_stack.size() - 1 です。

  ソースコード

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

struct Query {
    int type;
    long long x = 0;
    long long t = 0;
    long long u = 0;
};

struct Node {
    int l = 0, r = 0;
    int cnt = 0;
    __int128 sum = 0;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int Q;
    long long D;
    cin >> Q >> D;

    vector<Query> queries(Q);
    vector<long long> coords;
    vector<long long> last_stack;

    for (int i = 0; i < Q; i++) {
        int type;
        cin >> type;
        queries[i].type = type;

        if (type == 1) {
            long long x;
            cin >> x;
            queries[i].x = x;

            long long n = (long long)last_stack.size();
            long long T = x + D * (n + 1);
            long long U;

            if (n == 0) {
                U = T;
            } else {
                U = min(T, last_stack.back() + 2 * D);
            }

            queries[i].t = T;
            queries[i].u = U;

            coords.push_back(T);
            coords.push_back(U);
            last_stack.push_back(U);
        } else if (type == 2) {
            last_stack.pop_back();
        }
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());

    vector<Node> seg;
    seg.reserve((size_t)Q * 45 + 10);
    seg.push_back(Node());

    auto pull = [&](int id) {
        int l = seg[id].l;
        int r = seg[id].r;
        seg[id].cnt = seg[l].cnt + seg[r].cnt;
        seg[id].sum = seg[l].sum + seg[r].sum;
    };

    auto clone_node = [&](int id) -> int {
        seg.push_back(seg[id]);
        return (int)seg.size() - 1;
    };

    function<int(int,int,int,int,int)> point_add = [&](int id, int nl, int nr, int pos, int delta) -> int {
        int nid = clone_node(id);

        if (nl == nr) {
            seg[nid].cnt += delta;
            seg[nid].sum += (__int128)coords[pos] * delta;
            return nid;
        }

        int mid = (nl + nr) >> 1;
        if (pos <= mid) {
            seg[nid].l = point_add(seg[nid].l, nl, mid, pos, delta);
        } else {
            seg[nid].r = point_add(seg[nid].r, mid + 1, nr, pos, delta);
        }

        pull(nid);
        return nid;
    };

    function<int(int,int,int,int)> clear_greater = [&](int id, int nl, int nr, int k) -> int {
        if (id == 0 || nr <= k) return id;
        if (nl > k) return 0;

        int mid = (nl + nr) >> 1;
        int old_l = seg[id].l;
        int old_r = seg[id].r;

        int new_l = clear_greater(old_l, nl, mid, k);
        int new_r = clear_greater(old_r, mid + 1, nr, k);

        if (new_l == old_l && new_r == old_r) return id;

        int nid = clone_node(id);
        seg[nid].l = new_l;
        seg[nid].r = new_r;
        pull(nid);

        if (seg[nid].cnt == 0) return 0;
        return nid;
    };

    function<pair<int,__int128>(int,int,int,int)> query_greater = [&](int id, int nl, int nr, int k) -> pair<int,__int128> {
        if (id == 0 || nr <= k) return {0, 0};
        if (nl > k) return {seg[id].cnt, seg[id].sum};

        int mid = (nl + nr) >> 1;
        auto a = query_greater(seg[id].l, nl, mid, k);
        auto b = query_greater(seg[id].r, mid + 1, nr, k);
        return {a.first + b.first, a.second + b.second};
    };

    auto print_int128 = [](__int128 v) {
        if (v == 0) {
            cout << 0 << '\n';
            return;
        }

        if (v < 0) {
            cout << '-';
            v = -v;
        }

        string s;
        while (v > 0) {
            s.push_back(char('0' + v % 10));
            v /= 10;
        }
        reverse(s.begin(), s.end());
        cout << s << '\n';
    };

    vector<int> root_stack;
    root_stack.reserve(Q + 1);
    root_stack.push_back(0);

    int K = (int)coords.size();

    for (const auto& q : queries) {
        if (q.type == 1) {
            int root = root_stack.back();

            int kt = (int)(lower_bound(coords.begin(), coords.end(), q.t) - coords.begin());
            int ku = (int)(lower_bound(coords.begin(), coords.end(), q.u) - coords.begin());

            auto moved = query_greater(root, 0, K - 1, kt);
            root = clear_greater(root, 0, K - 1, kt);

            if (q.t == q.u) {
                root = point_add(root, 0, K - 1, kt, moved.first + 1);
            } else {
                if (moved.first > 0) {
                    root = point_add(root, 0, K - 1, kt, moved.first);
                }
                root = point_add(root, 0, K - 1, ku, 1);
            }

            root_stack.push_back(root);
        } else if (q.type == 2) {
            root_stack.pop_back();
        } else {
            long long n = (long long)root_stack.size() - 1;
            int root = root_stack.back();
            __int128 ans = seg[root].sum - (__int128)D * n * (n + 1) / 2;
            print_int128(ans);
        }
    }

    return 0;
}

---

この解説は gpt-5.5-high によって生成されました。