ABC389 - C - Snake Queue

問題

一旦クエリ$ 2が無いときに解けるかを考える。

クエリ$ 3で$ x番目のヘビの頭の座標を出力するとき、答えるのは$ 1匹目から$ x-1匹目のヘビの長さの合計値。

これは累積和配列を持っておけば高速に求められる。

以上を踏まえてクエリ$ 2を考える。

クエリ$ 2で実際に累積和配列を再計算していては間に合わない。

そこで何匹抜けたかだけを数えておいて、うまくクエリ$ 3を計算できないかを考える。

クエリ$ 2によって$ k匹のヘビが抜けたとき、

クエリ$ 3の$ x番目のヘビの頭の座標とは、$ k+1匹目から$ k+x匹目のヘビの長さの合計値。

これは累積和配列の差分で計算できるので、解けた。

code: c.py

Q = int(input())

k = 0

S = 0

ans = []

for _ in range(Q):

q = list(map(int, input().split())) + 0

q, x = q0, q1

if q == 1:

S.append(S-1 + x)

elif q == 2:

k += 1

else:

ans.append(Sx-1+k - Sk)

print(*ans, sep="\n")