de_dust2's blog

By de_dust2, history, 3 weeks ago, In English

Question 1 : Given an array of N elements handle below two type of range queries :

1. Update L R v : Replace each element in range [L, R] to v
2. Query X : Get value at position X

Question 2 : Given an array of N elements handle below two type of range queries :

1. Update L R v : Replace each element in range [L, R] to v
2. Query L R : Get max(or min/sum) of values in range [L, R]

Can someone kindly help me with the approach for above problems?

 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

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

I have a solution for both the problems if the constraints are lower like $$$10$$$$$$5$$$. We can use sqrt decomposition with some kind of lazy propagation.
Use simple sqrt decomp. Now coming to the update query,
1) if a block lies partially in the range $$$l$$$ to $$$r$$$ then linearly traverse and update.
2) Let's say we have two arrays 1) lazy a boolean array 2) val array to hold corresponding value to be put in case of lazy propagation.
now if the block lies completely then do lazy propagation. set $$$lazy[curblock]$$$ = true and $$$val[curblock]$$$ = $$$v$$$. So in this way you won't need to traverse the block and this will make the complexity of every query O(sqrt($$$N$$$)). Now rest is same as we do in lazy propagation in segment tree. You can calculate range min/max also using the same idea.

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

Segment Tree with Lazy Propagation, I think this might help https://usaco.guide/plat/RURQ

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

    Thank you. But what should be the combine function of segment tree in case of question 1? Could be any dummy function, is it?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Sure, you could use a sum function or whatever

      Here's my code if it helps

      Code