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.
The first line contains an integer n (1 ≤ n ≤ 10^5). The second line contains n integers: v1, v2, ..., vn (1 ≤ vi ≤ 10^9) — costs of the stones.
The third line contains an integer m (1 ≤ m ≤ 10^5) — 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.
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.
6
6 4 2 7 2 7
3
2 3 6
1 3 4
1 1 6
24
9
28
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
10
15
5
15
5
5
2
12
3
5
Please note that the answers to the questions may overflow 32-bit integer type.
题解：维护两个前缀和，原序sum1[]和有序sum2[],因为n (1 ≤ n ≤ 10^5)，(1 ≤ vi ≤ 10^9) ，所以n*v<=10^14，所以sum[]为long long 类型即可。剩下的m次询问，每次运行时间复杂度就为O(1),然后本题就得到解决。
代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdbool.h> 4 #include<stdlib.h> 5 #include<math.h> 6 #include<ctype.h> 7 #include<time.h> 8 9 #define rep(i,a,b) for(i=(a);i<=(b);i++) 10 #define red(i,a,b) for(i=(a);i>=(b);i--) 11 #define sqr(x) ((x)*(x)) 12 #define clr(x,y) memset(x,y,sizeof(x)) 13 #define LL long long 14 15 16 int i,j,n,m, 17 a[110000]; 18 19 LL sum1[110000],sum2[110000]; 20 21 void pre() 22 { 23 clr(a,0); 24 clr(sum1,0); 25 clr(sum2,0); 26 } 27 28 void sort(int head,int tail) 29 { 30 int i,j,x; 31 i=head;j=tail; 32 x=a[head]; 33 34 while(i<j) 35 { 36 while((i<j)&&(a[j]>=x)) j--; 37 a[i]=a[j]; 38 while((i<j)&&(a[i]<=x)) i++; 39 a[j]=a[i]; 40 } 41 42 a[i]=x; 43 44 if(head<(i-1)) sort(head,i-1); 45 if((i+1)<tail) sort(i+1,tail); 46 } 47 48 int init() 49 { 50 int i; 51 scanf("%d",&n); 52 rep(i,1,n){ 53 scanf("%d",&a[i]); 54 sum1[i]=sum1[i-1]+a[i]; 55 } 56 sort(1,n); 57 58 rep(i,1,n) 59 sum2[i]=sum2[i-1]+a[i]; 60 return 0; 61 } 62 63 int main() 64 { 65 int i,ty,x,y; 66 pre(); 67 init(); 68 69 scanf("%d",&m); 70 71 rep(i,1,m){ 72 scanf("%d%d%d",&ty,&x,&y); 73 if(ty==1) printf("%lld ",sum1[y]-sum1[x-1]); 74 else printf("%lld ",sum2[y]-sum2[x-1]); 75 } 76 77 return 0; 78 }