#CF433B. 栗山未来的石头

栗山未来的石头

CF433B Kuriyama Mirai's Stones

题目描述

\hspace{15pt}栗山未来已经杀死了许多怪物,并得到了许多(准确地说有 nn 个)宝石。她将这些宝石从 11 编号到 nn。第 ii 个宝石的价格是 viv_i。栗山未来想知道这些宝石的一些信息,因此她会向你提出两种类型的问题:

1. {\hspace{20pt}}_\texttt{1.}\,她会告诉你两个数字 ll 和 r(1≦l≦r≦n)r \left(1 \leqq l \leqq r \leqq n\right),你需要回答 ∑i=lrvi\sum_{i=l}^{r} v_i。

2. {\hspace{20pt}}_\texttt{2.}\,设 uiu_i 为第 ii 便宜的宝石的价格(即把所有宝石的价格非递减排序后,排在第 ii 位的价格)。这次她会告诉你两个数字 ll 和 r(1≦l≦r≦n)r \left(1 \leqq l \leqq r \leqq n\right),你需要回答 ∑i=lrui\sum_{i=l}^{r} u_i。

\hspace{15pt}每个问题你都需要给出正确答案,否则栗山未来会说“不愉快です”并且变得不高兴。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦105)n \left(1 \leqq n \leqq 10^5\right) 代表宝石的数量。

\hspace{15pt}第二行输入 nn 个整数 $v_1,v_2,\dots,v_n \left(1 \leqq v_i \leqq 10^9\right)$ 代表第 ii 个宝石的价格。

\hspace{15pt}第三行输入一个整数 m(1≦m≦105)m \left(1 \leqq m \leqq 10^5\right) 代表问题的个数。

\hspace{15pt}此后 mm 行,第 ii 行输入三个整数 $\mathrm{type},l,r \left(1 \leqq \mathrm{type} \leqq 2;\ 1 \leqq l \leqq r \leqq n\right)$ 描述一个问题。若 type=1\mathrm{type}=1,代表第一个问题;否则代表第二个问题。

输出格式

\hspace{15pt}输出 mm 行,第 ii 行输出一个整数,代表栗山未来提出的第 ii 个问题的答案。请按输入顺序输出答案。

测试样例

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

24
9
28

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

10
15
5
15
5
5
2
12
3
5

数据范围与提示

\hspace{15pt}请注意,答案可能会超出 3232 位整数范围。