C - Rotate and Sum Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

Q 個のクエリが与えられるので順に処理してください。クエリは 2 種類あり、以下のいずれかの形式で与えられます。

  • 1 c： A の先頭の要素を末尾に移動させる操作を c 回行う。
  • 2 l r： \displaystyle \sum_{i=l}^r A_i の値を出力する。

制約

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • 1\le A_i \le 10^9
  • 1\le c\le N
  • 1\le l\le r \le N
  • 2 つ目の形式のクエリが 1 つ以上存在する
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \ldots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリ \text{query}_i は以下の 2 種類のいずれかの形式で与えられる。

1 c

2 l r

出力

問題文の指示に従って 2 つ目の形式のクエリへの答えを改行区切りで出力せよ。

入力例 1

4 3
3 1 4 5
2 1 3
1 1
2 2 3

出力例 1

8
9

各クエリは以下のように処理されます。

  • 1 つ目のクエリ： A_1+A_2+A_3=3+1+4=8 なので 8 を出力します。
  • 2 つ目のクエリ： A=(3,1,4,5) が A=(1,4,5,3) に変化します。
  • 3 つ目のクエリ： A_2+A_3=4+5=9 なので 9 を出力します。

入力例 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

出力例 2

31
31
7
4

Score : 350 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

Process Q queries in order. There are two types of queries, given in the following formats:

  • 1 c: Perform the operation of moving the first element of A to the end c times.
  • 2 l r: Output the value of \displaystyle \sum_{i=l}^r A_i.

Constraints

  • 1\le N\le 2\times 10^5
  • 1\le Q\le 2\times 10^5
  • 1\le A_i \le 10^9
  • 1\le c\le N
  • 1\le l\le r \le N
  • At least one query of the second type exists.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query \text{query}_i is given in one of the following two formats:

1 c

2 l r

Output

Following the instructions in the problem statement, output the answers to the second type queries, separated by newlines.

Sample Input 1

4 3
3 1 4 5
2 1 3
1 1
2 2 3

Sample Output 1

8
9

Each query is processed as follows:

  • First query: A_1+A_2+A_3=3+1+4=8, so output 8.
  • Second query: A=(3,1,4,5) changes to A=(1,4,5,3).
  • Third query: A_2+A_3=4+5=9, so output 9.

Sample Input 2

5 7
1 2 4 8 16
2 1 5
1 4
1 5
2 1 5
2 2 4
1 1
2 3 3

Sample Output 2

31
31
7
4