AdditionalFile5130.zip

#5130. 「JOI Open 2025」冒泡排序机

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 JOI Open 2025 T1 「バブルソート機 / Bubble Sort Machine」

算法研究者 JOI 君开发了一种名为冒泡排序机的设备。

冒泡排序机是一种处理长度为 $N$ 的整数序列 $a = (a_{1}, a_{2}, \ldots, a_{N})$ 的设备。使用冒泡排序机时，首先需要输入每个 $a_{i}$ $(1 \leq i \leq N)$ 的初始值 $A_{i}$。然后，每次按下冒泡排序机的按钮 1，设备会按照以下方法改变整数序列 $a$：

• 按 $i=1, 2, \ldots, N-1$ 顺序执行：如果 $a_{i} > a_{i+1}$，则交换 $a_{i}$ 和 $a_{i+1}$ 的值。

JOI 君为了让冒泡排序机更具吸引力，决定为其增加以下功能：

• 按下按钮 2，并输入满足 $1 \leq l \leq r \leq N$ 的整数 $l, r$，设备会输出 $a_{l} + a_{l+1} + \cdots + a_{r}$。

给定输入冒泡排序机的整数序列初始值以及操作步骤的信息，你需要编写一个程序，计算冒泡排序机在每次按下按钮 2 时的输出值。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_{1}, A_{2}, \ldots, A_{N}$。

第三行包含一个整数 $Q$。

接下来 $Q$ 行，每行描述一次操作，包含 $1$ 个或 $3$ 个用空格分隔的整数。设每行的第一个整数为 $T_{j}$，则有：

• 若 $T_{j}=1$，该行无其他整数，表示第 $j$ 次操作是按下按钮 1。
• 若 $T_{j}=2$，该行后续包含两个整数 $L_{j}, R_{j}$，表示第 $j$ 次操作是按下按钮 2，并输入整数 $L_{j}, R_{j}$。

输出格式

对于每次按下按钮 2 的操作（即 $T_{j}=2$ 的第 $j$ $(1 \leq j \leq Q)$ 次操作），按顺序输出一行一个整数，表示冒泡排序机的输出值。

样例 1

输入

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

输出

13
3
12
5

首先输入初始值 $a_{1}=5, a_{2}=3, a_{3}=5, a_{4}=2$，初始化为 $a=(5, 3, 5, 2)$。接下来的冒泡排序机操作如下：

1. 按下按钮 2，输入 $l=1, r=3$，冒泡排序机输出 $a_{1} + a_{2} + a_{3} = 13$。
2. 按下按钮 1，对于 $i=1, 2, 3$ 按顺序执行以下操作：
   • 对于 $i=1$，$a_{1} > a_{2}$，因此交换值，$a$ 变为 $(3, 5, 5, 2)$。
   • 对于 $i=2$，$a_{2} > a_{3}$ 不成立，因此 $a$ 不变。
   • 对于 $i=3$，$a_{3} > a_{4}$ 成立，因此交换值，$a$ 变为 $(3, 5, 2, 5)$。
3. 按下按钮 2，输入 $l=1, r=1$，冒泡排序机输出 $a_{1} = 3$。
4. 按下按钮 2，输入 $l=2, r=4$，冒泡排序机输出 $a_{2} + a_{3} + a_{4} = 12$。
5. 按下按钮 1，对于 $i=1, 2, 3$ 按顺序执行以下操作：
   • 对于 $i=1$，$a_{1} > a_{2}$ 不成立，因此 $a$ 不变。
   • 对于 $i=2$，$a_{2} > a_{3}$ 成立，因此交换值，$a$ 变为 $(3, 2, 5, 5)$。
   • 对于 $i=3$，$a_{3} > a_{4}$ 不成立，因此 $a$ 不变。
6. 按下按钮 2，输入 $l=1, r=2$，冒泡排序机输出 $a_{1} + a_{2} = 5$。

这个样例满足子任务 $1, 5, 6$ 的限制。

样例 2

输入

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

输出

3
4
4

这个样例满足子任务 $1, 3, 5, 6$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 500000$
• $1 \leq A_{i} \leq 10^{9}$ $(1 \leq i \leq N)$
• $1 \leq Q \leq 500000$
• $T_{j}$ 为 $1$ 或 $2$ $(1 \leq j \leq Q)$
• 当 $T_{j}=2$ 时，$1 \leq L_{j} \leq R_{j} \leq N$ $(1 \leq j \leq Q)$
• 输入值均为整数。

详细子任务附加限制及分值如下表所示。