分数: 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