提出 #69756718

---

ソースコード 拡げる

"""
<方針>
- `A` の先頭を本当にぐるぐる移動 させてたら時間が足りない `O(NQ)`
- `A` を環状で考えてあげて（マージンをとって２倍にしておく）、先頭の移動は、`head` で管理させてあげれば良さそう。
- とはいえ、`[l, r)` を毎回計算していたら、これもまた `O(NQ)` になってしまう（一敗）。
- そこは累積和 `B` を用いて、あらかじめ計算しておき（`O(N)`）、`[0, r) - [0, l-1)` としてクエリ毎に計算（`O(Q)`）すれば良い。
- 全体として、`O(N+Q)` となった。
"""
N, Q = map(int, input().split())
A = list(map(int, input().split()))

# マージンをとって２倍
A = A[:] + A[:]

# 累積和を計算する。
B = [0]
for i in range(2*N):
  B.append(B[-1]+A[i])

# 先頭を管理する変数
head = 0

# クエリ毎の処理
for _ in range(Q):
  query = list(map(int, input().split()))
  match query:
    # 1, c のとき、
    case [1, c]:
      # 先頭を動かす
      head += c
      # 2*Nのサイズに収まるようにしておく
      head %= N
    # 2, l, r のとき、
    case [2, l, r]:
      # [0, r) - [0, l-1) を計算する。
      print(B[head+r] - B[head+l-1])

提出情報

ジャッジ結果