两种区间求和

课堂重述版 · 前缀和 · 来源：Codeforces 433B Kuriyama Mirai's Stones

题目描述

有 $n$ 块石头，第 $i$ 块石头的价格为 $v_i$。有 $m$ 次询问，每次给出类型 $t$ 和区间 $[l,r]$：

• 若 $t=1$，求原顺序下区间 $[l,r]$ 的价格之和；
• 若 $t=2$，先把所有价格按非递减顺序排列，再求排序后区间 $[l,r]$ 的价格之和。

输入格式

第一行一个整数 $n$。第二行 $n$ 个整数 $v_1,v_2,\dots,v_n$。第三行一个整数 $m$。接下来 $m$ 行，每行三个整数 $t,l,r$。

输出格式

对每个询问输出一行，表示对应的区间和。

数据范围与约定

$1 \le n,m \le 10^5$，$1 \le v_i \le 10^9$，$1 \le l \le r \le n$，$t \in \{1,2\}$。

样例输入

6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

样例输出

24
9
28

样例说明

排序后的价格为 $2,2,4,6,7,7$。$t=2,l=3,r=6$ 的和为 $4+6+7+7=24$；原序列 $[3,4]$ 的和为 $2+7=9$；原序列 $[1,6]$ 的和为 $28$。

说明

课堂重述题，数据由 src/gen.py 重新生成，和原站评测数据不同。