ABC425 C – Rotate and Sum Query

C - Rotate and Sum Query

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

長さNの整数列Aが与えられる。Q個のクエリを順に処理していく問題。

以降はA = [3, 1, 4, 5]を考えていく

クエリ1ではAの先頭を末尾に移動する操作した結果、先頭がどこかを保持する。これをxとしておく。操作回数はc。

初期値は0とし、c=1の場合、xは1になる。

初期値が0でc=5の場合、xは一周回って1になる。

なので、現在のxとcを足して配列の長さのあまりがクエリ１の操作後のxになる。

x = (x + c) % n

クエリ2はlからrまでの数値までの和。

ここでは累積和を使う。

l=1,r=3の場合、r から l-1の累積和の値を使うと9-0=9と求められる

この時先頭=xの値も考慮すると、x=1、l=1、r=3の場合、lとrがxの分加算されるので、14-3で合計は11になる。

lとrが整数列Aより大きくなることがあるので、Aを後ろに追加している

以下でACできました

def i_map():
    return map(int, input().split())


def i_list():
    return list(map(int, input().split()))

n, q = i_map()
a = i_list()

a = a+a

s = [0]
for i in range(2*n):
    s.append(s[i]+a[i])

x = 0
for i in range(q):
    query = i_list()
    if query[0] == 1:
        x = (x+query[1]) % n
    else:
        l, r = query[1], query[2]
        l = l+x
        r = r+x
        print(s[r]-s[l-1])Code language: Python (python)