CodeForces - 433B - Kuriyama Mir

*嗯，这题其实就是她给你两个类型，让你输出相应的答案；
类型1：输入数组直接进行累加
类型2：将输入数组排序然后进行累加

拿样例分析

6 //输入数组有几个数字
6 4 2 7 2 7 //输入数组
3 //有几个问题需要解答
t l r // t只有1和2代表她问的问题类型 l,r代表输出第l个到第r个的累加值
2 3 6
1 3 4
1 1 6

不多说了，上代码*

#include<stdio.h>
#include <algorithm>
using namespace std;

long long a[111111], v[111111], u[111111];  //a数组存输入的数值，v存第一类型累加值，u存第二类型累加值，在外部定义数组每一位初始值为0；
long long i, n, m, l, r, type;

void ini1()  //第一类型累加预处理
{
    scanf("%lld", &n);
    for (i = 0; i < n; i++)//累加
    {
        scanf("%lld", &a[i]);
        v[i+1] = a[i] + v[i];   // v[1] = a[0]+v[0];  v[2] = a[1]+v[1]...可知v[1] = a[1], v[2]=a[2]+a[1]...以此类推  
    }
}

void ini2() //第二类型累加预处理
{
    sort(a, a+n); // 将输入数组排序
    for (i = 0; i < n; i++)
        u[i+1] = a[i] + u[i];
}

int main()
{
    ini1(); //问题1初始化
    ini2(); //问题2初始化
    scanf("%lld", &m);
    while(m--)
    {
        scanf("%lld%lld%lld", &type, &l, &r);
        if (type == 1)//判断方案
            printf("%lld\n", v[r]-v[l-1]); 因为数组下标未位移量，所以从3累加到6是4个数字，所以减去l-1而不是l
        else
            printf("%lld\n", u[r]-u[l-1]);
    }
    return 0;
}

时间复杂度是线性的

第一篇题解，有不足之处，请见谅。