AcWing 4789. 前缀和序列
原题链接
中等
作者:
秋似火
,
2023-06-05 18:28:10
,
所有人可见
,
阅读 174
题目描述
**定义两个数组Sa与Sb,分别存储排序前与排序后的前缀和。数据类型使用long long**
C++ 代码
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
using namespace std;
// 原题来自ACWing 4789
const int N = 10e5 + 5;
int n, m;
long long a[N], sa[N], sb[N];
int main() {
int ret = scanf("%d", &n);
for (int i = 1;i <= n;i++)ret = scanf("%lld", &a[i]);
ret = scanf("%d", &m);
//构造a的前缀和
for (int i = 1;i <= n;i++) {
sa[i] = sa[i - 1] + a[i];
}
sort(a, a + n + 1);
//构造b的前缀和
for (int i = 1;i <= n;i++) {
sb[i] = sb[i - 1] + a[i];
}
while (m--) {
int q, l, r;
ret = scanf("%d%d%d", &q, &l, &r);
if (q == 1) printf("%lld\n", sa[r] - sa[l - 1]);
else printf("%lld\n", sb[r] - sb[l - 1]);
}
return 0;
}