IITKESOA3P1 - Sub array Sum1
Let A = {a0, a1, a2, a3, ...., an−1} be an array. We define a recursive operation Op on array A as follows
Op(A) = Op(two(A)) + Op(one(A)) + Op(zero(A)) if n > 1
= A otherwise
Here, zero(A) = {a0, a3, a6, ..} i.e. an array formed by elements whose indices are divisible by 3. Similarly, one(A) = {a1, a4, a7, a10, ...} and two(A) = {a2, a5, a8, a11..}. Also, + is the concatenation operation.
For example, if A = {0, 1, 2, 3, 4, 5}. Then Op(A) will be calculated as
Op(A) = Op({2, 5}) + Op({1, 4}) + Op({0, 3})
= Op({}) + Op({5}) + Op({2}) + Op({}) + Op({4}) + Op({1}) + Op({}) + Op({3}) + Op({0})
= {5, 2, 4, 1, 3, 0}
We define an query on an array B as taking the sum of all elements bk where i ≤ k ≤ j and l ≤ bk ≤ r.
Input
First line contains size n of array C. ( n ≤ 10^5 ) -
Second line contains n integers c0, c1, c2, ...cn−1. ( |ci | < 10^6 ) -
Third line contains q, number of queries. (q ≤ 10^5 ) -
Next q lines contains four integers i, j, l, r. (0 ≤ i < n, i ≤ j < n, l = −10^6 − 1, r = 10^6 + 1)
Note that l, r are fixed
Output
You have to output q integers corresponding to each query on a separate line.
Example
Input: 4 1 -1 5 4 1 0 3 -1000001 1000001 Output: 9
Added by: | Programming Club, IITK |
Date: | 2017-03-21 |
Time limit: | 1s-2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |