Given an array A consist of N integers. (N <= 10^5). There are Q (Q <= 10^5) queries of two types:
1 x y: Increase x smallest elements, each by 1 which satisfy the following condition: all elements greater than or equal to y. (1 <= x <= N, 0 <= y <= 10^9).
2 l r: Count the number of elements in array A have value in range [l..r]. (1 <= l <= r <= 10^9).
I haven't found an approach to process queries type 1 yet. Could someone help me? Thanks.
Sort the initial array and use segment tree with lazy propagation.
Lets say your array is now 2 3 4 4 4 4 4 5 6 7 and you have to increase the first 5 elements
You can binary search for the last element that has the same value as the xth element and update like this.
(2+1) (3+1) 4 4 (4+1) (4+1) (4+1) 5 6 7
It can be done with 2 range updates.
The array maintains monotone.
For queries of type 2 just do binary search
Im not sure what you mean about that y thing but i think you can deal with it with binary search.
If the array is 2 3 4 4 4 4 4 5 6 7 then if x = 3 and y = 5 you have to increase the last three elements.
But I understood your idea, I think it's correct. Thanks for your help.
Got accepted. Many thanks, I learnt new technique today.
can u post the link to the original problem .
how to find the list of elements which we have to increase
You can use segment tree with binary search.
Assume that you want to find the position of the last element <= val. Then you look at right node, if minimum value of right node <= val then jump to right node, else jump to left node
https://oj.uz/problem/view/BOI11_grow
Baltic Olympiad In Informatics 2011 Task Grow
For query 1 , after sorting the array , we will find the lower bound of y in the array and we will also get the index of that element (say lb) , now we update the the range lb to lb+x-1 (0-based indexing) using lazy prop.! correct me if I'm wrong and also how to answer the type 2 query ?