分数: 400 点
问题陈述
给你一个序列 A=(A_1,A_2,\dots,A_N) 长度 N.
流程 Q 按顺序查询。 每个查询均采用以下格式之一:
1 x:交换以下值 A_x 和 A_{x+1}.2 l r:查找值 \displaystyle \sum_{l\leq i\leq r} A_i.
约束
- 2\leq N \leq 2\times 10^5
- 1\leq Q \leq 5\times 10^5
- 1\leq A_i \leq 10^4
- 对于第一类查询, 1\leq x \leq N-1.
- 对于第二种类型的查询, 1\leq l\leq r \leq N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
A_1 A_2 \dots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, \text{query}_i 代表 i-第一个查询,并以下列格式之一给出:
1 x
2 l r
输出
让 q 为第二类查询的数量,输出 q 行。 的 i第行 (1\leq i \leq q) 应包含以下问题的答案 i第二类型的第一个查询。
示例输入 1
4 4 2 7 1 8 1 2 2 1 2 1 1 2 2 4
示例输出 1
3 17
- 在 1-st 查询,交换以下值 A_2 和 A_3。这使得 A=(2,1,7,8).
- 在 2-nd查询,找到的值 A_1+A_2。答案是 2+1=3.
- 在 3-rd 查询,交换值 A_1 和 A_2。这使得 A=(1,2,7,8).
- 在 4-第次查询,找到值 A_2+A_3+A_4。答案是 2+7+8=17.
示例输入 2
8 10 22 75 26 45 72 81 47 29 2 2 7 2 6 8 2 4 4 1 2 2 1 3 1 1 2 2 4 1 2 1 4 2 1 1
示例输出 2
346 157 45 123 142 26