_Bunny's blog

Lazy
By _Bunny, history, 2 years ago, In English

Problem: Given an array a1, a2, ..., an (1 <= n <= 1e6) and q queries, for each query has two types.

1 l r x: a[i] = min(a[i], x) (l <= i <= r).

2 i : print value in position i.

I dont know use lazy update to solve operator 1, help me pls (sorry i'm poor E).

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

Comments Comments (4)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

instead of setting tree[id].min value to x just set it to min(tree[id].min, x)

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

tr[x].val = min (tr[x] . val , v);

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Above problem can be solved using a simple segment tree, without doing lazy propagation since the operation 1 is commutative.

To learn "Lazy propagation" you can refer to "Segment Tree, part-2" of Edu section.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

You don't need lazy, Use the approach of the cses Range Update Queries.

Here: Code

→ Reply