Lazy Propagation

plz reply

Your update function is incorrect.

can u plz give me a test case where my code would fail.

Think carefully about why you are performing each step. You will quickly find your mistake if you think about what you are doing. This is a very important skill to learn.

i have another problem with lazy propagation method :

suppose we have 4 kind of updates operation consequently, and then a query for a range result . so 4 update should be done on some ranges one by one , but i think having 4 updates consequently on big intervals don't allow to updates done one by one on small intervals and this cause a problem.
let's see an example on FlipConis Problem (codechef.com/problems/FLIPCOIN) :

6 5
0 0 6
0 0 3
0 2 5
0 1 6
1 1 6

so what's the order of updates ? when updates done on small intervals ??
i'm so confused about how several updates done one by one.

sorry for my poor english
thanks

another issue !

i think this problem (FlipCoin) maybe can be solved by this kind of lazy propagation , but imagine we have 3 TYPE of update operations (like problem: uva.onlinejudge.org/external/114/11402.html) , so what should we do on this ?

When updating you only update until you reach a node where you are updating the entire range, then you flag it for update.

When querying, of you reach a node that is flagged for update, then you perform the update on it and push the flag for update to it's children.

0 0 6
Update value in 0,6 and turn flag for update on.
0 0 3
Push update from 0,6 to 0,3 and 4,6 and update their values.
Update value in 0,3 and turn flag for update off.
0 2 5
Update value in 2,3 and turn flag for update on.
Push update from 4,6 to 4,5 and 6,6 and update their values.
Update value in 4,5 and turn flag for update off.
0 1 6
Update value in 1,1 and turn flag for update on.
Update value in 2,3 and turn flag for update off.
Update value in 4,6 and turn flag for update on.
1 1 6
Return value from 1,1
Return value from 2,3
Return value from 4,6

If you have read the rest of the topic you know that whenever I have an update flag set on a node it's value is correct but every node below it needs to be updated.

As for the other problem that you posted, it's nt that difficult. You just need to get more creative with your update flag.

@leppy :
can you please have a look at this code implementing the idea you suggested earlier in this post. Its working fine for me but giving WA on LITE problem testcases.

resolved, nice thread on lazy prop.
thanks!

was buggy: removed.

if(p==0) update(0, 1, lim, q, r);  
else if(p==1) cout<<get(0,1,lim,q,r)<<endl;

Use S instead of lim.