P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

译自 [JOI Open 2025](https://contests.ioi-jp.org/open-2025/index.html) T1「[Bubble Sort Machine](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/cm7aghex)」/ 「[バブルソート機](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/gkrcwais)」。

JOI 君——一名算法工程师，开发了冒泡排序机。 冒泡排序机操作长为 $N$ 的整数序列 $a=(a_1,a_2,\ldots,a_N)$。为了让机器能工作，给定 $A_i$ 作为 $a_i$（$1\le i\le N$）的初值。每当机器上的**按钮壹**被按下时，机器会按照如下方式修改序列 $a$： > 对于 $i=1,2,\ldots,N-1$（按此顺序），若 $a_i\gt a_{i+1}$，交换 $a_i,a_{i+1}$ 的值。 为了使冒泡排序机更博人眼球，JOI 君决定加入以下功能： > 当**按钮贰**被按下时，给定整数 $l,r$ 作为输入（须满足 $1\le l\le r\le N$），机器会输出 $a_{l}+a_{l+1}+\cdots+a_r$ 的值。 给定整数序列的初值和冒泡排序机的操作序列，编程计算按钮贰的输出值。

输入格式如下所示： > $N$ \ > $A_1$ $A_2$ $\cdots$ $A_N$ \ > $Q$ \ > $(\text{Query }1)$ \ > $(\text{Query }2)$ \ > $\vdots$ \ > $(\text{Query }Q)$ 这里，$Q$ 指的是冒泡排序机的操作数。每个 $(\text{Query }j)$（$1\le j\le Q$）由若干个空格分隔的数字组成。令 $T_j$ 为 $(\text{Query }j)$ 的首个数字。这行的内容为以下二者之一： - 若 $T_j=1$，这行再没有其他整数了。这意味着冒泡排序机的第 $j$ 次操作按下了按钮壹。 - 若 $T_j=2$，接下来还有两个整数，依次是 $L_j,R_j$。这意味着冒泡排序机的第 $j$ 次操作按下了按钮贰，给定的输入为 $L_j,R_j$。

对每个按下按钮贰的操作［意思是，对每个满足 $T_j=2$ 的 $j$（$1\le j\le Q$）］，输出一行一个整数，表示冒泡排序机的输出。你的输出应与询问的顺序相符。

### 样例解释 #### 样例 $1$ 解释 初值为 $a_1=5,a_2=3,a_3=5,a_4=2$，$a=(5,3,5,2)$。接下来在冒泡排序机上操作： 1. 按下按钮贰，输入 $l=1,r=3$。机器输出 $a_1+a_2+a_3=13$。 2. 按下按钮壹。对 $i=1,2,3$，按此顺序进行如下操作： - $i=1$：由于 $a_1\gt a_2$，交换二者的值，操作后 $a=(3,5,5,2)$。 - $i=2$：由于并没有 $a_2\gt a_3$，不操作 $a$。 - $i=3$：由于 $a_3\gt a_4$，交换二者的值，操作后 $a=(3,5,2,5)$。 3. 按下按钮贰，输入 $l=1,r=1$。机器输出 $a_1=3$。 3. 按下按钮贰，输入 $l=2,r=4$。机器输出 $a_2+a_3+a_4=12$。 5. 按下按钮壹。对 $i=1,2,3$，按此顺序进行如下操作： - $i=1$：由于并没有 $a_1\gt a_2$，不操作 $a$。 - $i=2$：由于 $a_2\gt a_3$，交换二者的值，操作后 $a=(3,2,5,5)$。 - $i=3$：由于并没有 $a_3\gt a_4$，不操作 $a$。 6. 按下按钮贰，输入 $l=1,r=2$。机器输出 $a_1+a_2=5$。 样例 $1$ 满足子任务 $1,5,6$ 的限制。 #### 样例 $2$ 解释 样例 $2$ 满足子任务 $1,3,5,6$ 的限制。 ### 数据范围 - $2\le N\le 500\, 000$； - $1\le A_i\le 10^9\, (1\le i\le N)$； - $1\le Q\le 500\, 000$； - $T_j\in \{1,2\}\, (1\le j\le Q)$； - 若 $T_j=2$，有 $1\le L_j\le R_j\le N\, (1\le j\le Q)$； - 输入的值都是整数。 ### 子任务 - $\text{Subtask 1 (5 pts)}$：满足 $T_j=1$ 的 $j\,(1\le j\le Q)$ 至多有 $10$ 个； - $\text{Subtask 2 (11 pts)}$：$N,Q\le 150\, 000$，当 $T_j=2$ 时 $L_j=R_j=1\, (1\le j\le Q)$； - $\text{Subtask 3 (15 pts)}$：$N,Q\le 150\, 000$，$1\le A_i\le 2\, (1\le i\le N)$； - $\text{Subtask 4 (23 pts)}$：$N,Q\le 150\, 000$，当 $T_j=2$ 时 $L_j=R_j\, (1\le j\le Q)$； - $\text{Subtask 5 (29 pts)}$：$N,Q\le 150\, 000$； - $\text{Subtask 6 (17 pts)}$：无额外限制。