There is garden which contains N water fountains, each placed at distance 1 to N Each water fountain Every morning Q people come to Walk in garden. People are represented as follow L R K : Each people drink water from fountain numbered L to R and reduce their water level to max (0,A[i]-K) Assuming people come in serial order, find the count of fountains with zero total water level after each person.
Problem Constraints 1 <= N, Q <= 10 ^ 5 1 <= A[i], K <= 10 ^ 9 1<=L<=R<=N
First argument of input contains integer array A of size N. Second argument of input contains Qx3 integer matrix denoting people.
Example Input
Input A=[5,7,3] B=[[1, 2, 1],[2, 3, 1],[1,3,4]]
Input 2: A=[1] B=[1, 1, 10]
Output 1 [0,0,2]
output 2 [1]
You can use segment trees with lazy Propagation
How will you check that which level is zero after each operation? I am taking sum of levels of fountains in the segment tree than applying lazy propagation on that.
That too can be found through segment tree as well, maintaing how many zero elements are there in a segment and updating it after each operation
How would you update that lazily?
I think you can use the idea of sqrt-decomposition.
For $$$i$$$-th block of size $$$B$$$, let's store the sorted vector of numbers $$$v_i$$$ in that block and store $$$add_i$$$ — the amount of water reduced for that block.
When we want to calculate the number of fountains with positive amount of water, for $$$i$$$-th block we will calculate the number of $$$v_{i, j}$$$ such that $$$v_{i, j}$$$ is not less than $$$add_i$$$ (with binary search).
When we want to update the subarray, we will update the value of $$$add_j$$$ for the blocks that are within our subarray.
For other blocks that intersect our subarray (their number is maximum two), we will re-update their vector and $$$add_j$$$ value. We will make straightforwardly with $$$O(B* \log B)$$$ time complexity.
Total time complexity is around $$$O(Q * (\frac{N}{B} + B) * \log B)$$$, the value $$$B$$$ should be chosen carefully around the $$$\sqrt{N}$$$. But that time complexity actually can be slow.
Can you provide the source of the problem?
Sorry for my bad English.
Can u please provide the code ????
hey did you get code ?
You can use parallel binary search. You can also do persistent segment tree, but I prefer parallel binary search.
Alternative solution. Keep the people in a segment tree. Now when you want to find the answer for fountain at index i, only active people who have i in their interval. After that, do a binary search on activated people. This one is in $$$O(N log N)$$$ while the previous 2 are in $$$O(N log^2 N)$$$
Edit: There is also a solution with segment tree beats and this one is actually online and $$$O(Q log N)$$$. Basically, build a segment tree on fountains and on each node keep track of how much water needs to be taken from it for any fountain under it to become empty. That way you can find all the fountains which get emptied in $$$O(log N)$$$ per fountain after each query. The nice thing is that you might need to find each fountain only once, so complexity of this part amortizes to $$$O(N log N)$$$