← 返回题目列表

AtCoder · abc442_d

G. 交换和范围总和

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

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