codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

433B.md (2262B)


      1 Source: https://codeforces.com/problemset/problem/433/B
      2 
      3 B. Kuriyama Mirai's Stones
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 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 *v**i*. Kuriyama Mirai wants to know something about these stones so she will ask you two kinds of questions:
     22 
     23 1. She will tell you two numbers, *l* and *r* (1 ≤ *l* ≤ *r* ≤ *n*), and you should tell her ![](https://espresso.codeforces.com/6a950b27de2103bb53df10f9ace817ae3df57fa9.png).
     24 2. Let *u**i* 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 ![](https://espresso.codeforces.com/9830c0af1b3d14c66843c32f7c106c97428b7d2d.png).
     25 
     26 For every question you should give the correct answer, or Kuriyama Mirai will say "fuyukai desu" and then become unhappy.
     27 
     28 Input
     29 
     30 The first line contains an integer *n* (1 ≤ *n* ≤ 105). The second line contains *n* integers: *v*1, *v*2, ..., *v**n* (1 ≤ *v**i* ≤ 109) — costs of the stones.
     31 
     32 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.
     33 
     34 Output
     35 
     36 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.
     37 
     38 Examples
     39 
     40 Input
     41 
     42 ```
     43 6  
     44 6 4 2 7 2 7  
     45 3  
     46 2 3 6  
     47 1 3 4  
     48 1 1 6
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 24  
     55 9  
     56 28
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 4  
     63 5 5 2 3  
     64 10  
     65 1 2 4  
     66 2 1 4  
     67 1 1 1  
     68 2 1 4  
     69 2 1 2  
     70 1 1 1  
     71 1 3 3  
     72 1 1 3  
     73 1 4 4  
     74 1 2 2
     75 ```
     76 
     77 Output
     78 
     79 ```
     80 10  
     81 15  
     82 5  
     83 15  
     84 5  
     85 5  
     86 2  
     87 12  
     88 3  
     89 5
     90 ```
     91 
     92 Note
     93 
     94 Please note that the answers to the questions may overflow 32-bit integer type.