### LuckyPaper's blog

By LuckyPaper, history, 7 months ago, ,

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.

•
• +8
•

 » 7 months ago, # | ← Rev. 2 →   +13 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 elementsYou 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 7It can be done with 2 range updates.The array maintains monotone. For queries of type 2 just do binary searchIm not sure what you mean about that y thing but i think you can deal with it with binary search.
•  » » 7 months ago, # ^ |   +1 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.
•  » » 7 months ago, # ^ |   0 Got accepted. Many thanks, I learnt new technique today.
•  » » » 7 months ago, # ^ |   +3 can u post the link to the original problem .
•  » » » » 7 months ago, # ^ |   0 how to find the list of elements which we have to increase
•  » » » » » 7 months ago, # ^ |   0 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
•  » » » » 7 months ago, # ^ |   +12 https://oj.uz/problem/view/BOI11_growBaltic Olympiad In Informatics 2011 Task Grow
 » 7 months ago, # |   0 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 ?