시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 43 | 3 | 3 | 7.500% |
You are given an array $A$ consisting of $n$ integers. All its elements are numbered with consecutive integers from $1$ to $n$. Your task is to process $m$ queries. Each of these queries is one of the following kinds:
Your task is to implement a proper data structure to process $m$ given queries for a given array $A$.
First line of input contains the only integer $n$ --- the initial size of the array $A$ ($1 \leq n \leq 2 \cdot 10^{5}$).
Second line of input contains $n$ non-negative integers $A_{i}$ --- elements of the array $A$ ($0 \leq A_{i} \leq 10^{9}$).
Third line of input contains the only integer $m$ --- the number of queries ($1 \leq m \leq 2 \cdot 10^{5}$).
Each of the following lines contains a separate query in the following format:
For any query of the first or the third kind $0 \leq x_{j} \leq 10^{9}$. For any query of the second kind $l_{j}$ and $r_{j}$ do not violate bounds of the array $A$.
You may assume that at least one query in each test case is of the second kind.
For each query of the second kind output its resulting sum on a separate line.
5 3 4 7 3 6 7 3 5 2 2 4 4 1 15 2 3 6 3 1 2 1 6
9 30 33