P76029 两种顺序的区间和 — 题解

专题： 前缀和
适用题目： 新生 OJ 本地题包中的 P76029，不要直接用于外站同名题。

解题思路

分别建立原数组和排序后数组的前缀和，根据询问类型选择正确的一套。

复杂度

排序 $O(n\log n)$，前缀构建 $O(n)$，每问 $O(1)$。

易错点

排序副本不能覆盖原数组用于第一类查询的数据。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

int cmp_ll_asc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (a > b) - (a < b);
}
int cmp_ll_desc(const void *p, const void *q) {
    long long a = *(const long long *)p, b = *(const long long *)q;
    return (b > a) - (b < a);
}

int main(void) {
    int n,q;scanf("%d",&n);
    long long *a=malloc(n*sizeof(long long));
    long long *pre=calloc(n+1,sizeof(long long)),*sp=calloc(n+1,sizeof(long long));
    for(int i=0;i<n;i++){scanf("%lld",&a[i]);pre[i+1]=pre[i]+a[i];}
    qsort(a,n,sizeof(long long),cmp_ll_asc);
    for(int i=0;i<n;i++)sp[i+1]=sp[i]+a[i];
    scanf("%d",&q);
    while(q--){int type,l,r;scanf("%d%d%d",&type,&l,&r);
        long long *p=type==1?pre:sp;
        printf("%lld\n",p[r]-p[l-1]);
    }
    free(a);free(pre);free(sp);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n;
    vector<ll>a(n+1),p(n+1),sp(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p[i]=p[i-1]+a[i];
    }
    sort(a.begin()+1,a.end());
    for(int i=1;i<=n;i++)sp[i]=sp[i-1]+a[i];
    cin>>q;
    while(q--){
        int type,l,r;
        cin>>type>>l>>r;
        auto &v=(type==1?p:sp);
        cout<<v[r]-v[l-1]<<nl;
    }
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。