problem.txt (2065B)
1 B. Kuriyama Mirai's Stones 2 time limit per test 3 2 seconds 4 memory limit per test 5 256 megabytes 6 7 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: 8 9 She will tell you two numbers, l and r (1 ≤ l ≤ r ≤ n), and you should tell her . 10 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 . 11 12 For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy. 13 Input 14 15 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. 16 17 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. 18 Output 19 20 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. 21 22 --- 23 24 - n stones 25 - 1 -> n 26 - cost of ith is v_i 27 - query types 28 1. sum 29 - l,r 30 - l <= r 31 - sum from l to r 32 2. u_i cost of ith cheapest stone l and r where we sum over these 33 - basically, sum on ordered list non-decreasing 34 35 - n, n integers (costs), m (number of questions), questions (type, l, r) 36 37 n = 6 38 costs = 6 4 2 7 2 7 39 question count = 3 40 41 q1 = 2 3 6 42 q2 = 1 3 4 43 q3 = 1 1 6 44 45 2 3 6 is ordered sum from index 2 to 5 46 47 [2, 2, 4, 6, 7, 7] 48 49 sum(4, 6, 7, 7) = 24 50 51 ...