【cf433B】Kuriyama Mirai's Stones

描述 Description

Kuriyama Mirai has killed many monsters and got many (namely n) stones. She numbers the stones from 1 to n. The cost of the i-th stone is vi. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:

She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her .

Let ui be the cost of the i-th cheapest stone (the cost that will be on the i-th place if we arrange all the stone costs in non-decreasing order). This time she will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her .

For every question you should give the correct answer, or Kuriyama Mirai will say “fuyukai desu” and then become unhappy.

输入格式 InputFormat

The first line contains an integer n (1 ≤ n ≤ 105). The second line contains n integers: v1, v2, …, vn (1 ≤ vi ≤ 109) — costs of the stones.
The third line contains an integer m (1 ≤ m ≤ 105) — the number of Kuriyama Mirai’s questions. Then follow m lines, each line contains three integers type, l and r (1 ≤ l ≤ r ≤ n; 1 ≤ type ≤ 2), describing a question. If type equal to 1, then you should output the answer for the first question, else you should output the answer for the second one.

输出格式 OutputFormat

Print m lines. Each line must contain an integer — the answer to Kuriyama Mirai’s question. Print the answers to the questions in the order of input.

样例输入 SampleInput

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

样例输出 SampleOutput

10
15
5
15
5
5
2
12
3
5

数据范围和注释 Hint

Please note that the answers to the questions may overflow 32-bit integer type.

Codeforces 433B

代码 Code

水。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff
long long i,j,t,n,m,l,r,k,z,y,x,s;
long long a[100001],b[100001];
long long sa[100001],sb[100001];
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sa[i]=sa[i-1]+a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    scanf("%d",&m);
    for (i=1;i<=n;i++) sb[i]=sb[i-1]+b[i];
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&s,&l,&r);
        if (s==1)cout<<sa[r]-sa[l-1];
        if (s==2)cout<<sb[r]-sb[l-1];
        cout<<endl;
    }
    return 0;
}