besher's blog

DS problem
By besher, 10 years ago, In English

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:

  1. set the lower bound of numbers from L to R to k.

  2. 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).

  3. 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.

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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...

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 .

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

I know the guy in real life, and he explained this problem in our mother-tongue and still couldn't understand it :D

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you understand it now :p

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is o() ?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It's Big O notation, you can learn about complexity using your favorite search engine :D

        → Reply