Overview

For the sequence of buildings at each point in time, we find the maximum sum of the adjusted heights that satisfy the constraints.
Since the operations consist of adding to the right end and deleting from the right end, we can manage the optimal height sequence as a “stack” and process deletions quickly by reverting to past states.

Discussion

First, let us consider a fixed sequence of buildings \(C_1, C_2, \dots, C_M\).

If the adjusted height sequence \(B\) satisfies the conditions, then for any \(i, j\):

\[ B_i \leq B_j + D|i-j| \leq C_j + D|i-j| \]

must hold.

Therefore, the height at each position \(i\) must always satisfy:

\[ A_i = \min_j \left(C_j + D|i-j|\right) \]

or less.

Conversely, if we choose this \(A_i\) directly as \(B_i\), it satisfies:

• \(A_i \leq C_i\)
• The difference between adjacent elements is at most \(D\)

Thus, the optimal adjusted height is:

\[ B_i = A_i = \min_j \left(C_j + D|i-j|\right) \]

and the answer is:

\[ \sum_i A_i \]

---

Naive Approach is Too Slow

If we compute \(A_i\) for all buildings every time operation 3 is called, the time complexity becomes \(O(Q^2)\) in the worst case, which is too slow for \(Q \leq 10^5\).

Therefore, let’s consider how the optimal height sequence \(A\) changes when a building is added to the right end in operation 1.

Let \(n-1\) be the current number of buildings, and \(x\) be the height of the newly added building.

The constraint imposed by the new building for position \(i\) is:

\[ H_i = x + D(n-i) \]

Thus, the new optimal value becomes:

\[ A'_i = \min(A_i, H_i) \]

However, for the new position \(n\), the value coming only from the existing buildings is:

\[ A_{n-1} + D \]

An important observation here is that \(A_i - H_i\) is monotonically non-decreasing from left to right.
This is because the difference between adjacent elements of \(A\) is at most \(D\), so:

\[ A_{i+1} - A_i \geq -D \]

which implies:

\[ (A_{i+1} - H_{i+1}) - (A_i - H_i) = (A_{i+1} - A_i) + D \geq 0 \]

Therefore, the part affected by the new building is always a contiguous interval at the right end, i.e., a “suffix”.

For example, if the constraint of the new building takes effect from some position \(q\) onwards:

\[ A'_i = \begin{cases} A_i & (i < q) \\ x + D(n-i) & (i \geq q) \end{cases} \]

Thus, in operation 1, we only need to perform the following:

• Add a value to the right end
• Remove a certain suffix and replace it with a new arithmetic progression

Algorithm

We manage the optimal height sequence \(A\) as a set of intervals, each representing an arithmetic progression.

Each interval is of the following form:

\[ [l, r], \quad A_i = \text{val} + \text{slp} \times (i-l) \]

Here, the slope \(\text{slp}\) is basically \(D\) or \(-D\).

For each interval, we maintain the following:

• L, R : Left and right ends of the interval
• VAL : Value at the left end
• SLP : Slope
• SUM : Cumulative sum up to this interval
• UP : Pointer for doubling to the previous interval
• BOT : The leftmost interval of the block being looked at in doubling

---

Operation 1 x

Let the current length be \(n-1\) and the new length be \(n\).

1. Compute the value of the new position using only existing constraints

Letting last be the current optimal value at the right end, the value at position \(n\) coming only from the existing buildings is:

\[ \text{old\_ext} = \text{last} + D \]

If

\[ \text{old\_ext} \leq x \]

holds, the height limit of the new building does not take effect.
Therefore, we simply append old_ext to the right end.

2. When the new building constraint takes effect

If

\[ \text{old\_ext} > x \]

holds, the constraint of the new building takes effect at the right end.

The value due to the new building is:

\[ H_i = x + D(n-i) \]

First, we find the first position \(q\) where:

\[ A_i > H_i \]

Since the constraint of the new building takes effect from \(q\) onwards:

\[ A'_i = H_i \]

Therefore, we remove the parts of the existing intervals from \(q\) onwards, and add the interval:

\[ [q, n] \]

with the arithmetic progression of slope \(-D\):

\[ H_q, H_q-D, H_q-2D, \dots, x \]

---

How to Find the Boundary \(q\)

While we could find \(q\) by scanning the intervals from right to left, this would take \(O(Q^2)\) in the worst case.

Therefore, we maintain the sequence of intervals as a persistent linked list and use doubling.

UP[k][v] represents the interval reached by going back \(2^k\) steps from interval v.
BOT[k][v] is the leftmost interval of that block of \(2^k\) intervals.

Since \(A_i - H_i\) is monotonically non-decreasing, if

\[ A_i > H_i \]

at the leftmost position of a block, then the entire block is affected by the new building.

Using this property, we can find the parts that can be removed in large blocks from the right end, and finally compute \(q\) within the interval containing the boundary.

Within the interval \([l, r]\), if we can write:

\[ A_i = \text{val} + \text{slp}(i-l) \]

then

\[ A_i - H_i \]

is also an arithmetic progression.

Letting the difference at the left end be:

\[ g_l = \text{val} - \left(x + D(n-l)\right) \]

the common difference of the difference is:

\[ \text{slp} + D \]

Therefore, the first position \(q\) where the difference becomes positive can be found by:

\[ q = l + \left\lfloor \frac{-g_l}{\text{slp}+D} \right\rfloor + 1 \]

---

Operation 2

We delete the building at the right end.

This can be done by reverting to the state just before the last operation 1.

In the code, just before operation 1, we save:

• root
• length

to a history stack.

In operation 2, we pop these values and restore the state.

---

Operation 3

The sum of the current optimal height sequence is stored in the SUM of the last interval.

Therefore, we only need to output:

SUM[root]

If it is empty, root = 0, and since SUM[0] = 0, this case is handled naturally.

Complexity

• Time Complexity: \(O(Q \log Q)\)
  • Operation 1: \(O(\log Q)\)
  • Operation 2: \(O(1)\)
  • Operation 3: \(O(1)\)
• Space Complexity: \(O(Q \log Q)\)

Implementation Points

The sum of each interval is calculated as the sum of an arithmetic progression.

Letting the interval length be:

\[ \text{cnt} = r-l+1 \]

the sum of the interval is:

\[ \text{cnt} \times \text{val} + \text{slp} \times \frac{\text{cnt}(\text{cnt}-1)}{2} \]

Also, if adjacent intervals have the same slope and their values connect continuously, we merge them:

if prev and SLP[prev] == slp and VAL[prev] + slp * (l - L[prev]) == val:
    ...

This helps keep the number of intervals small.

Since the values can reach up to around \(10^{14}\), you should use long long when implementing in C++. In Python, integers have arbitrary precision, so no special care is needed.

Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    Q = int(next(it))
    D = int(next(it))
    negD = -D

    LOG = (2 * Q + 10).bit_length()

    L = [0]
    R = [0]
    VAL = [0]
    SLP = [0]
    SUM = [0]

    UP = [[0] for _ in range(LOG)]
    BOT = [[0] for _ in range(LOG)]

    def add_node(l, r, val, slp, prev):
        idx = len(L)
        L.append(l)
        R.append(r)
        VAL.append(val)
        SLP.append(slp)
        cnt = r - l + 1
        SUM.append(SUM[prev] + cnt * val + slp * cnt * (cnt - 1) // 2)

        UP[0].append(prev)
        BOT[0].append(idx)
        for k in range(1, LOG):
            mid = UP[k - 1][idx]
            if mid:
                UP[k].append(UP[k - 1][mid])
                BOT[k].append(BOT[k - 1][mid])
            else:
                UP[k].append(0)
                BOT[k].append(0)
        return idx

    def append_seg(prev, l, r, val, slp):
        if prev and SLP[prev] == slp and VAL[prev] + slp * (l - L[prev]) == val:
            return add_node(L[prev], r, VAL[prev], slp, UP[0][prev])
        return add_node(l, r, val, slp, prev)

    root = 0
    length = 0
    hist_root = []
    hist_len = []
    ans = []

    for token in it:
        typ = int(token)

        if typ == 1:
            x = int(next(it))
            hist_root.append(root)
            hist_len.append(length)

            n = length + 1

            if length == 0:
                root = append_seg(0, 1, 1, x, negD)
                length = 1
                continue

            last = VAL[root] + SLP[root] * (R[root] - L[root])
            old_ext = last + D

            if old_ext <= x:
                root = append_seg(root, n, n, old_ext, D)
                length = n
                continue

            cur = root
            for k in range(LOG - 1, -1, -1):
                b = BOT[k][cur]
                if b and VAL[b] > x + D * (n - L[b]):
                    cur = UP[k][cur]

            if cur == 0:
                prefix = 0
                q = 1
            else:
                l = L[cur]
                r = R[cur]
                sl = SLP[cur]
                vr = VAL[cur] + sl * (r - l)
                dr = vr - (x + D * (n - r))

                if dr <= 0:
                    prefix = cur
                    q = r + 1
                else:
                    dl = VAL[cur] - (x + D * (n - l))
                    step = sl + D
                    q = l + ((-dl) // step + 1)
                    p = q - 1
                    prefix = add_node(l, p, VAL[cur], sl, UP[0][cur])

            val_q = x + D * (n - q)
            root = append_seg(prefix, q, n, val_q, negD)
            length = n

        elif typ == 2:
            root = hist_root.pop()
            length = hist_len.pop()

        else:
            ans.append(str(SUM[root]))

    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.