← 返回题目列表

AtCoder · abc425_c

E. 循环和求和查询

中文机器翻译题面 查看原题

分数: 350 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N.

流程 Q 按顺序查询。有两种类型的查询,以下列格式给出:

  • 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
  • 至少存在一个第二类型的查询。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

每个查询 \text{query}_i 以以下两种格式之一给出:

1 c
2 l r

输出

按照问题陈述中的说明,输出第二类查询的答案,以换行符分隔。


示例输入 1

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

示例输出 1

8
9

每个查询的处理方式如下:

  • 第一个查询: A_1+A_2+A_3=3+1+4=8,所以输出 8.
  • 第二个查询: A=(3,1,4,5) 更改为 A=(1,4,5,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