← 返回题单
题单练习 前缀和
← 上一题 下一题 →

A5383 | 双前缀求和

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。把它升序排序后得到数组 $b$（与 $a$ 的元素相同、只是顺序不同）。

你需要回答 $m$ 次区间求和询问。每次询问给出三个整数 $t, \ell, r$（$1\le \ell \le r \le n$）：

若 $t=1$，回答原数组区间和：$a_\ell + a_{\ell+1} + \cdots + a_r$；

若 $t=2$，回答排序后数组区间和：$b_\ell + b_{\ell+1} + \cdots + b_r$。

输入格式

  • 第一行：一个整数 $n$。
  • 第二行：$n$ 个整数，表示数组 $a_1,a_2,\dots,a_n$。
  • 第三行：一个整数 $m$。
  • 接下来 $m$ 行：每行三个整数 $t,\ \ell,\ r$。

输出格式

输出共 $m$ 行。第 $i$ 行输出第 $i$ 次询问的答案。

输入输出样例

输入 #1
5
5 1 2 3 2
4
1 2 4
2 2 4
1 1 5
2 1 3
输出 #1
6
7
13
5
C++ 编辑器
输入
输出