kaium.'s blog

By kaium., history, 5 months ago, In English,

How can i solve that problem? please help...i know about lazy segment tree...but i am failed to apply lazy segment tree... problem link-> : https://www.spoj.com/problems/MULTQ3/

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all instead of storing the numbers just store the modulos. That is each A[i] change it to A[i] % 3. This way you just have to deal with 3 numbers 0, 1 and 2.

In the tree node store an array cnt[0..2] this stores the count of all the numbers with such mods for that Range.

In the lazy node store the pending updates % 3. ( See yourself why )

When updating lazily Apply the pending updates.

  • If there is no pending update do nothing,

  • If there is 1 pending update change. (like cnt[1] will become cnt[0], cnt[2] = cnt[1] and cnt[0] = cnt[2] )

  • If there are 2 pending updates swap(cnt[2], cnt[0] ) and cnt[1] won't be affected.

Finally answer for a range is just summing cnt[0]'s for appropriate ranges ( like standard sum query)

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks..iamrk

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks iamrk . good approach.

    can u explain, if there is 1 pending update part.

    cnt[1] --> cnt[2] bcoz of initial pending and from cnt[2] ---> cnt[0] bcoz of current operation. is this bcoz of it that cant[1] is becoming cnt[0] and same for others.