DS problem - Codeforces

Блог пользователя besher

DS problem

Автор besher, 11 лет назад, По-английски

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.

data structures, problem

besher
11 лет назад
8

Комментарии (8)

Написать комментарий?

P_Nyagolov

11 лет назад, скрыть # |

Hi, can you please provide a link to the problem because I find it really hard to understand the statement.

→ Ответить

besher

11 лет назад, скрыть # ^ |

← Rev. 3 →

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

→ Ответить