Can anyine solve this problem? Problem Link
Time limit: 1.00 s Memory limit: 512 MB
Statement
You have n coins with positive integer values. The coins are numbered 1, 2, ...., n. Your task is to process q queries of the form: "if you can use coins a ..... b, what is the smallest sum you cannot produce?"
Input
The first input line has two integers n and q: the number of coins and queries. The second line has n integers x_1, x_2, ......., x_n: the value of each coin. Finally, there are q lines that describe the queries. Each line has two values a and b: you can use coins a .... b.
Output
Print the answer for each query.
Constraints
- n , q <= 1e5
- x_i <= 1e9
- 1 <= a <= b <= n
Example Input:
5 3
2 9 1 2 7
2 4
4 4
1 5
Output:
4
1
6
Explanation: First you can use coins [9,1,2], then coins [2] and finally coins [2,9,1,2,7].
Auto comment: topic has been updated by lohitpt252003 (previous revision, new revision, compare).
did you solve the previous range query problems ?
No. This question was given in a quiz and I was not able to solve it.
i think you can find mex — minimal number, which not in range, for like prefix, then the anwser should be max(prefix[a], prefix[b]) probably, try that. I see that problem so interesting, i'm going to do them)lohitpt252003
Could u elaborate ur idea and write implement it?
Assuming there are $$$m$$$ ones in the interval, the initial sum you can produce is then the range $$$[1,m]$$$. You will find that you can add all the numbers within $$$(1,m+1]$$$ to your set of available coins. If their sum is $$$s$$$, the range of values you can now form is $$$[1,m+s]$$$. Following this, you can incorporate the coins from the interval $$$(m+1,m+s+1]$$$, and so on. This process is repeated until no new coins can be found with the current range $$$[1, m' + s']$$$. The answer is then $$$m'+s'+1$$$. This process will iterate only $$$O(\log V)$$$ times.
To implement this, you will clearly need a data structure that supports prefix sum queries. Furthermore, it may be necessary to query historical versions of the data (as each prefix can be considered a version). Seems to be a persistent segment tree (maybe with dynamic node creation).
The time complexity of this approach is $$$O(q \log^2 V).$$$ idk if it's fast enough though... and the implementation would be quite complex, so I'd hope there's a more "beautiful" way.
It worked thanx btw!
pastebin link