codeforces433B

Kuriyama Mirai's Stones

 CodeForces - 433B 

有n颗宝石，每个宝石都有自己的价值。

 

然后m次询问。问区间[i,j]的宝石的总值，或者问排序后的区间[i,j]的总值。

 

Input第一行输入一个n(1 <= n <=10^5)，表示n个宝石

 

第二行n个数，v1, v2, ..., vn (1 ≤ vi ≤ 10^9) ，表示每个宝石的价值

 

第三行输入询问次数m（1≤m≤10^5)。

 

然后m行，每行包含三个整数类型，type、l和r（ 1 ≤ l ≤ r ≤n；1 ≤ type≤ 2）

 

描述一个问题。如果类型等于1，则应输出原序列的答案，

 

否则应输出排序后的答案。

 

Output打印M行。每行必须包含一个整数-对Kuriyama Mirai问题的答案。按输入顺序打印问题的答案。

 

Examples

Input

6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6

Output

24
9
28

Input

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

Output

10
15
5
15
5
5
2
12
3
5

sol：大水题，维护两串前缀和即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=100005;
int n,Q;
ll a[N],b[N];
ll Qzha[N],Qzhb[N];
int main()
{
    int i;
    R(n);
    for(i=1;i<=n;i++) a[i]=b[i]=read();
    for(i=1;i<=n;i++) Qzha[i]=Qzha[i-1]+a[i];
    sort(b+1,b+n+1);
    for(i=1;i<=n;i++) Qzhb[i]=Qzhb[i-1]+b[i];
    R(Q);
    while(Q--)
    {
        int opt=read(),l=read(),r=read();
        switch (opt)
        {
            case 1:
                Wl(Qzha[r]-Qzha[l-1]);
                break;
            case 2:
                Wl(Qzhb[r]-Qzhb[l-1]);
                break;
        }
    }
    return 0;
}
/*
input
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
output
10
15
5
15
5
5
2
12
3
5
*/