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.
Hi, can you please provide a link to the problem because I find it really hard to understand the statement.
I try to solve 500E - New Year Domino using this DS ... I know it has a much more easier solution than mine ... but I want to know if i could solve it using this DS.
I will try to describe it more:
there is three operations which you have to do it:
1- S L R K : set every number less than K from L to R to K.
2- D L R K : decrease the value of numbers between L and R by K ... after this operation is done every number is less than zero we will increase its cost by its negative value just like that:
for (int i=0;i<n;++i) { cost[i]+=max(0,-a[i]); a[i]=max(0,a[i]); }
3- Q K : print the cost of K-th number
As much as I appreciate your innovation here, but your DS problem is a lot more harder than the original problem :D, it's an overkill...
but I want to know if I could implement this DS with o(log n) per operation ... that's why I didn't mention the problem .
I know the guy in real life, and he explained this problem in our mother-tongue and still couldn't understand it :D
you understand it now :p
what is o() ?
It's Big O notation, you can learn about complexity using your favorite search engine :D