shayan.p's blog

By shayan.p, history, 5 weeks ago, In English,

Hello every one... I need a data structure handling two type of queries. 1. Maximize(l,r,x) 2. Sum(l,r)

I have a O(sqrt(n)*log(n)) solution using sqrt decomposition + set.But I am looking for a better solution. Thanks in advance

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

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

Auto comment: topic has been updated by shayan.p (previous revision, new revision, compare).

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

Maximise (l,r,x) means set a[i] = max(a[i], x) ?

»
5 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was awesome. Thank you!

    Btw do you have any link to Chinese trick like this?

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

It's possible sqrt decomposition in this case without logarithmic factor? (Lazy sqrt decomposition or dsu approach? Yeah... segment tree beats is cool)

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

    By setting a proper bucket size, you can achieve per query.

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

      Yeah, I know...,but with potential function analyze (7'-'). u.u maybe, I hope :v