시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 183 | 80 | 63 | 52.066% |
The house prices have been going up and the Virtual County Tax Collection Agency needs help to keep track of prices.
We assume the houses in Virtual County (VC) are numbered 1 through n, i.e., the house numbers are 1, 2, 3, …, n. VC keeps track of the house prices as they go up and would like to know the total price for different sections of the county, e.g., the total price for houses 4 through 15.
The first input line contains an integer, n (1 ≤ n ≤ 5 ×105), indicating the number of houses in VC. Each of the next n input lines contains an integer (between 1 and 109, inclusive) indicating the initial price for a house; first integer is the price for the first house, second integer is the price for the second house, etc.
After the initial price information for all the houses, the input will have a set of transactions (operations) to be processed. This section of the input starts with an integer, t (1 ≤ t ≤ 105), indicating the number of transactions. Each of the next t input lines contains a transaction to be processed. There will be two types of transactions:
There is no output required for Update transactions. For each Retrieve transaction, output a separate line providing the total price for the range being requested.
5 100 200 150 300 250 8 R 2 4 U 2 20 U 3 40 R 2 4 R 1 5 U 2 10 U 4 100 R 1 5
650 710 1060 1170