_Bunny's blog

Lazy
By _Bunny, history, 4 months 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

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

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

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

From now, lazy is also a new category just like greedy

→ Reply
»
4 months ago, # |
  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