Overview

While adding and removing buildings at the right end, we want to find the maximum sum of heights at each step, given that we are only allowed to decrease heights and the adjacent differences must be at most \(D\).

The key idea is that instead of working with the heights directly, if we transform them by adding \(D i\) to the position \(i\), the update during an addition becomes an operation of “decreasing all values larger than a certain value to that value.”

Analysis

Let \(M\) be the current number of buildings, \(C_i\) be the original heights, and \(B_i\) be the adjusted heights.

The conditions are as follows:

\[ 0 \leq B_i \leq C_i \]

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

If we handle this directly, the optimal height of the entire sequence might change every time we add a building.
Calculating the optimal values for all buildings each time would take \(O(Q^2)\) in the worst case, which is too slow for \(Q \leq 10^5\).

Therefore, we consider the following transformation:

\[ A_i = B_i + D i \]

We also transform the upper bound of the original height:

\[ T_i = C_i + D i \]

Then, \(B_i \leq C_i\) becomes:

\[ A_i \leq T_i \]

Furthermore, rewriting the adjacency condition:

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

becomes:

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

and:

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

becomes:

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

In other words, the transformed \(A_i\) must satisfy:

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

Also, the value we want to find is:

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

So we just need to output:

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

---

Now, suppose we know the current optimal \(A_1, A_2, \dots, A_n\).
Let’s add a new building to the right end, and let its transformed upper bound be:

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

The new optimal values can be updated as follows:

• All existing values become \(\min(A_i, T)\)
• The new last value becomes \(\min(T, A_n + 2D)\)

That is:

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

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

This is because in the new sequence, due to the monotonicity \(A_i \leq A_{i+1}\), all existing values must also be less than or equal to the new last value, which is at most \(T\).
Thus, any existing values greater than \(T\) must be decreased to \(T\).

Additionally, the new last element must satisfy the difference condition with its predecessor:

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

Therefore, the addition operation essentially becomes:

1. Change all current \(A_i\) that are larger than \(T\) to \(T\).
2. Add the new value \(U = \min(T, A_n + 2D)\).

This is the key observation.

Algorithm

We manage the current optimal \(A_i\) as a multiset.
We do not need their exact order, but rather the following operations:

• Count how many values are larger than \(T\)
• Delete them
• Add \(T\) that many times
• Add the new last value \(U\)
• Find the current \(\sum A_i\)

To perform this quickly, we build a persistent segment tree over the coordinate-compressed values.

Addition Operation

Let \(n\) be the current number of buildings, and \(x\) be the height of the new building.

Since the new position is \(n+1\):

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

Also, if the current last optimal value is \(last\), the newly added last value is:

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

However, if we are adding to an empty sequence:

\[ U = T \]

On the segment tree, we do the following:

1. Count the number of values larger than \(T\)
2. Delete all values larger than \(T\)
3. Add \(T\) that many times
4. Add one \(U\)

In the code, if \(T = U\), we add them to \(T\) together.

Deletion Operation

Buildings are always deleted from the right end.
This means the entire operation can be treated like a stack.

Therefore, we store the root of the segment tree at each step in a stack.

• In the addition operation, we create a new root and push it to the stack.
• In the deletion operation, we pop from the root stack.

By using a persistent segment tree, we can create a new state without destroying past states.

Query Operation

Let S be the \(\sum A_i\) stored in the current root.
If the current number of buildings is \(M\), the answer is:

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

Complexity

• Time Complexity: \(O(Q \log Q)\)
• Space Complexity: \(O(Q \log Q)\)

For each addition operation, we perform updates and queries on the persistent segment tree in \(O(\log Q)\) time.
Deletion and query operations are essentially \(O(1)\).

Implementation Points

• The values of \(T\) and \(U\) can be up to around \(10^{14}\), so long long is required.

• Since \(\sum A_i\) and intermediate products can become very large, we safely use __int128 in the code.

• For coordinate compression, we read all queries first and precalculate \(T\) and \(U\) for each addition operation.

• To rollback during deletion operations, we use a persistent segment tree instead of a regular segment tree.

• The current number of buildings can be found from the size of the root stack. Specifically, it is root_stack.size() - 1.

  Source Code

#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;
}

---

This editorial was generated by gpt-5.5-high.