ある \(2\) つ目の形式のクエリに対する答えを求めることを考えます。このクエリの答えは \(\displaystyle \sum_{i=l}^r A_i\) です。

ここで、長さ \(2N\) の整数列 \(B\) を \(B=(A_1,A_2,\ldots,A_N,A_1,\ldots,A_N)\) として定義します。つまり、 \(1\) つ目の形式のクエリにより変更される前の \(A\) を \(2\) つ連結した整数列を \(B\) とします。

すると、\(\displaystyle \sum_{i=l}^r A_i\) の値は「そのクエリまでの間に \(1\) つ目の形式のクエリで与えられた \(c\) の総和を \(N\) で割ったあまり」を \(C\) として \(\displaystyle \sum_{i=l+C}^{r +C} B_i\) と表すことができます。 \(B\) の要素はクエリによって不変なので、この値は累積和を用いることで計算することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+Q)\) です。

実装例(Python3)

import sys
input = sys.stdin.readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
b = a + a
for i in range(2 * n - 1, 0, -1):
    b[i - 1] += b[i]
rui_c = 0
for _ in range(q):
    query = list(map(int, input().split()))
    if query[0] == 1:
        c = query[1]
        rui_c += c
        rui_c %= n
    else:
        l, r = query[1] - 1, query[2]
        print(b[l + rui_c] - b[r + rui_c])