I wonder if you could help me solving this problem:
there is N items and initially all of them is 0 ... and for each item there is a cost value which is also initially 0.
you have to implement a data structure which can do this operations in o(log n) time:
set the lower bound of numbers from L to R to k.
decrease the value of numbers from L to R by v ... and each number become negative we increase the cost of it by its negative value and set its value to zero again (ex. after decreasing a number become -5 we increase the cost of this number by 5 and set the value of this number to 0).
print the cost of the k-th number.
I try to implement it using segment tree .. but I found a problem in lazy propagation...
any help would be appreciated ... sorry for my bad english .
thanks.
Full text and comments »