M - ビルの高さ調整 / Adjusting Building Heights Editorial by admin
gpt-5.5-high概要
各時点のビル列に対して、制約を満たす調整後の高さの合計最大値を求めます。
操作は右端への追加・右端からの削除なので、最適な高さ列を「スタック」として管理し、削除は過去の状態へ戻すことで高速に処理します。
考察
まず、固定されたビル列 \(C_1, C_2, \dots, C_M\) について考えます。
調整後の高さ列 \(B\) が条件を満たすなら、任意の \(i, j\) について
\[ B_i \leq B_j + D|i-j| \leq C_j + D|i-j| \]
が成り立ちます。
したがって、各位置 \(i\) の高さは必ず
\[ A_i = \min_j \left(C_j + D|i-j|\right) \]
以下でなければなりません。
逆に、この \(A_i\) をそのまま \(B_i\) として選ぶと、
- \(A_i \leq C_i\)
- 隣り合う差は高々 \(D\)
を満たします。
つまり、最適な調整後の高さは
\[ B_i = A_i = \min_j \left(C_j + D|i-j|\right) \]
であり、答えは
\[ \sum_i A_i \]
です。
素朴にやると遅い
操作 3 のたびに全ビルについて \(A_i\) を計算すると、最悪で \(O(Q^2)\) になり、\(Q \leq 10^5\) では間に合いません。
そこで、操作 1 で右端にビルを追加したとき、最適な高さ列 \(A\) がどう変化するかを考えます。
現在のビル数を \(n-1\)、新しく追加するビルの高さを \(x\) とします。
新しいビルが作る制約は、位置 \(i\) に対して
\[ H_i = x + D(n-i) \]
です。
つまり、新しい最適値は
\[ A'_i = \min(A_i, H_i) \]
になります。
ただし、新しい位置 \(n\) については、既存のビルだけから来る値は
\[ A_{n-1} + D \]
です。
ここで重要なのは、\(A_i - H_i\) は左から右へ見たとき単調非減少になることです。
なぜなら、\(A\) は隣り合う差が高々 \(D\) なので、
\[ A_{i+1} - A_i \geq -D \]
であり、
\[ (A_{i+1} - H_{i+1}) - (A_i - H_i) = (A_{i+1} - A_i) + D \geq 0 \]
となるからです。
したがって、新しいビルの影響を受ける部分は、必ず右端側の連続した区間、つまり「 suffix 」になります。
例えば、ある位置 \(q\) 以降で新しいビルの制約が効くなら、
\[ A'_i = \begin{cases} A_i & (i < q) \\ x + D(n-i) & (i \geq q) \end{cases} \]
となります。
つまり、操作 1 では
- 右端に値を追加するだけ
- ある suffix を削って、新しい等差数列に置き換える
という処理だけを行えばよいです。
アルゴリズム
最適な高さ列 \(A\) を、区間ごとの等差数列として管理します。
各区間は次の形です。
\[ [l, r], \quad A_i = \text{val} + \text{slp} \times (i-l) \]
ここで、傾き \(\text{slp}\) は基本的に \(D\) または \(-D\) です。
各区間について以下を持ちます。
L,R: 区間の左右端VAL: 左端での値SLP: 傾きSUM: その区間までの累積和UP: 前の区間へのダブリング用ポインタBOT: ダブリングで見ているブロックの一番左の区間
操作 1 x
現在の長さを \(n-1\) とし、新しい長さを \(n\) とします。
1. 既存の制約だけで新しい位置の値を計算
現在の右端の最適値を last とすると、既存のビルだけから来る位置 \(n\) の値は
\[ \text{old\_ext} = \text{last} + D \]
です。
もし
\[ \text{old\_ext} \leq x \]
なら、新しいビルの高さ制限は効きません。
そのため、単に右端に old_ext を追加します。
2. 新しいビルが効く場合
もし
\[ \text{old\_ext} > x \]
なら、新しいビルの制約が右端側で効きます。
新しいビルによる値は
\[ H_i = x + D(n-i) \]
です。
最初に
\[ A_i > H_i \]
となる位置 \(q\) を探します。
\(q\) 以降は新しいビルの制約が効くので、
\[ A'_i = H_i \]
になります。
したがって、既存の区間列のうち \(q\) 以降を削除し、区間
\[ [q, n] \]
に対して
\[ H_q, H_q-D, H_q-2D, \dots, x \]
という傾き \(-D\) の等差数列を追加します。
境界 \(q\) の探し方
区間を右から順に見ていけば \(q\) は見つかりますが、それでは最悪 \(O(Q^2)\) になります。
そこで、区間列を永続的な連結リストとして持ち、さらにダブリングを用います。
UP[k][v] は、区間 v から \(2^k\) 個前へ戻った先を表します。
BOT[k][v] は、その \(2^k\) 個の区間ブロックの一番左の区間です。
\(A_i - H_i\) は単調非減少なので、あるブロックの一番左の位置で
\[ A_i > H_i \]
なら、そのブロック全体が新しいビルの影響を受けます。
この性質を使って、右端から大きなブロック単位で削れる部分を探し、最後に境界を含む区間内で \(q\) を計算します。
区間 \([l, r]\) 内で
\[ A_i = \text{val} + \text{slp}(i-l) \]
と書けるとき、
\[ A_i - H_i \]
も等差数列になります。
左端での差を
\[ g_l = \text{val} - \left(x + D(n-l)\right) \]
とすると、差の公差は
\[ \text{slp} + D \]
です。
よって、最初に正になる位置 \(q\) は
\[ q = l + \left\lfloor \frac{-g_l}{\text{slp}+D} \right\rfloor + 1 \]
で求められます。
操作 2
右端のビルを削除します。
これは直前の操作 1 の状態に戻せばよいです。
コードでは、操作 1 の直前に
rootlength
を履歴スタックに保存しています。
操作 2 では、それを取り出して復元します。
操作 3
現在の最適な高さ列の合計は、最後の区間の SUM に入っています。
したがって、答えは
SUM[root]
を出力するだけです。
空の場合は root = 0 であり、SUM[0] = 0 なのでそのまま対応できます。
計算量
- 時間計算量: \(O(Q \log Q)\)
- 操作
1: \(O(\log Q)\) - 操作
2: \(O(1)\) - 操作
3: \(O(1)\)
- 操作
- 空間計算量: \(O(Q \log Q)\)
実装のポイント
各区間の和は等差数列の和として計算します。
区間長を
\[ \text{cnt} = r-l+1 \]
とすると、区間和は
\[ \text{cnt} \times \text{val} + \text{slp} \times \frac{\text{cnt}(\text{cnt}-1)}{2} \]
です。
また、隣り合う区間が同じ傾きで、値も自然につながる場合はマージします。
if prev and SLP[prev] == slp and VAL[prev] + slp * (l - L[prev]) == val:
...
これにより、区間数を抑えられます。
値は最大で \(10^{14}\) 程度になるため、C++ で実装する場合は long long を使う必要があります。Python では整数が任意精度なのでそのままで問題ありません。
ソースコード
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()
この解説は gpt-5.5-high によって生成されました。
posted:
last update: