Kuriyama Mirai's Stones
有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=;
bool f=;
char ch=' ';
while(!isdigit(ch))
{
f|=(ch=='-'); ch=getchar();
}
while(isdigit(ch))
{
s=(s<<)+(s<<)+(ch^); ch=getchar();
}
return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
if(x<)
{
putchar('-'); x=-x;
}
if(x<)
{
putchar(x+''); return;
}
write(x/);
putchar((x%)+'');
return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('\n')
const int N=;
int n,Q;
ll a[N],b[N];
ll Qzha[N],Qzhb[N];
int main()
{
int i;
R(n);
for(i=;i<=n;i++) a[i]=b[i]=read();
for(i=;i<=n;i++) Qzha[i]=Qzha[i-]+a[i];
sort(b+,b+n+);
for(i=;i<=n;i++) Qzhb[i]=Qzhb[i-]+b[i];
R(Q);
while(Q--)
{
int opt=read(),l=read(),r=read();
switch (opt)
{
case :
Wl(Qzha[r]-Qzha[l-]);
break;
case :
Wl(Qzhb[r]-Qzhb[l-]);
break;
}
}
return ;
}
/*
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
*/