GSS4 spoj TLE

Can anyone help me implement lazy propogation in this segment tree code??
i just can’t get it.

ok, try this

1: use binary index tree to update value

2: make use of this fact that a number will be reduced to 1 (by repetitive square root operation) in around 5-6 max operations
so for an x to y, don’t traverse from x to y, use some branching technique like

take an example… query is 2 to 9 and i know 4,5,6,7 are already reduced to 1…
i’ll execute this query as…
reduce 2 to its square root … what is next of 2… ok 3
reduce 3 to its square root … what is next of 3 which is not 1, ok 8
reduce 8 to its square root … what is next of 8 which is not 1, ok 9
reduce 9 to its square root … i am done with query.

so initial queries will take time but slowly they’ll get reduce.
hope so i explained properly? :confused:
if i didn’t please ask where i was not clear

Enjoy :smiley:

1 Like

the problem is that the update operations are over a given interval [a;b]. Let us consider that we have some number in the array K = 1<<64 = 18446744073709551616. This is quite big in fact and there might not be any numbers so big.
sqrt(1<<64) = 1<<32, sqrt(1<<32) = 1<<16, sqrt(1<<16) = 1<<8, …sqrt(1<<1) = 1<<0 = 1, sqrt(1<<1) = 1. Just after 7 operations we reached the bottom. So what can happen in the worst case if we do update operations over each element. We will just do 7 * n*log(n) updates and then we won’t to do any at all. => we can approach the updates naively, but if we have only 1s in a given segment, then we shouldn’t do any updates since this won’t change anything because sqrt(1) = 1.
For this, void update(int idx, int sfrom, int sto, int qfrom, int qto) {long long ss = (long long)sto - (long long)sfrom + 1LL; if (tree[idx].sum == ss) return;… rest update function}

i guess you are using inbuilt sqrt function for updating the array that is leading to TLE… try some faster sqrt calculations. :slight_smile:

1 Like

This too is giving TLE .

This too is giving TLE

getting TLE repeatedly guys…it would be great if anyone can tell me how would i get accepted.

Why can’t segment Tree be used here??

well, i am not getting how are you updating a range for an update query…
as in i used lazy propagation in queries like…

i have to set some value for each node… or something ,somewhere i have some pattern

i am not getting how you are updating a range… thats why i used BIT :confused:

1 Like

well here we can’t use lazy propagation because sqrt(x1+x2)!=sqrt(x1)+sqrt(x2)

yeah… right! , this is what i was saying :smiley:

So, here we can’t use segment tree(no lazy propagation)… did you get AC with BIT??