@shisuko , and others who solved.I just saw the setters approach for DRGNDEN(July long challenge) , and found the same approach and strategy I did.Tell me isn’t the solution taking O(4log(2n)) for a single update query, update at entry and exit for both direction. and since length of segment tree after flattening has become of length 2n after flattening. So for q update it will take O(4qlog(2n)). and since n and q both are upto 200000 4qlog(2*n)=14,887,712 . Dividing it by 10000000 , It gives 1.4 sec. Some solution got passed under 1s because testcase may have less no of updates, but I think you shoul agree, the question had very tight constraint, also if all the query would be of only updates, A/C to constraint , It shouldn’t pass the original subtask. Correct me , If I am wrong anywhere. See my Implementation here. Also tell me If I have done something wrong or I could have optimized the approach more.
You can do better. Update should take O(log n) complexity. In my solution for N = 10 power 5, for any update, it may take 17 iterations.
So, 2 lakhs * 17 = 34 lakhs, pretty good to get AC within given TC.
I used Segment tree + some preprocessing
No rule 1 we don’t count constants while counting for time complexity
so complexity rounds down to O(n) time to generate precomputed data and O (q log(n)) to run all queries. since n ~= q we can say solution is O ( n log(n) ). which is well under given time limit.
Yes I know , we don’t count constants while counting complexity, but I tried a lot but after lot of attempts when stucking on last subtasks, I left after doing these computation, thought there is some better approach, but later I found, the original approach , that tester had thought for this was the same. Anyway my bad…
Divide it by 10^8 and not by 10^7…(10^8 operations ~ 1s)
If it was the case , then my solution shouldn’t give TLE. As It takes O(4*log(n)) for update and O(log(n)) for sum.I think it is 10000000 query only ,which can pass in 1 s
Help me please
Help me Please
could you mind supporting me
Maybe your analysis is wrong…
Nope…if that was the case N*log(N) solutions with N = 10^6, should always TLE when TL = 1s
Do you want to know how i solved this problem?
Ill keep it as simple as i can, you should have been able to understand though if you know what segment trees are…
First if you have studied the problem, should know that one thing that doesn’t change is height.
and hieght defines path. thus path never changes in the problem through out execution. so we can have some precomputed data based upon them.
in our polyline from any point we can move from hight to lower point which can be either in right or left, if we make a graph for this movemet, you will end up with a graph consisting of cycles. (which i thought was not helpful)
but, if you make two graphs one to store movements from left to right and another for movement from right to left. you will have discrete trees (not graphs anymore) strating from local maximax of the whole polyline.
you can add a node zero to all the roots of these local maximas and now you have two mega trees, one for movement from left to right and another for right to left.
e.g. > this is input for height ( because we are working on paths at the moment )
3 1 4 1 5
if you want to move left to right you can go like this :-
1 → 2
3 → 4
nowhere from 5.
and for right to left movement
5 → 4
5 → 3
3 → 2
3 → 1
there are two discrete trees in movement from left to right, but only one for right to left.
if we add zero node these trees would look something like this.
to generate this tree you can use graharm scan on our array / vector of heights.
Here is a psuedo code for the same .
LRtree = left to right movement tree
RLtree = right to left movement tree
H = vector of heights
s = stack
push 0 into stack. // our mega root node, we can insert all local maximas into this one.
loop for i in range 1 to N:
loop while H[stack -> top] <= H[i] and stack has more than one element: // we would never want to take remove 0 from our stack.
pop one element from stack
end while loop
insert i as child of node (stack - > top) in LR tree
push i into stack.
end for loop.
s = new stack.
push 0 into stack // for the same reason i commented above.
loop for i in range N to 1:
loop while H[stack -> top] <= H[i] and stack has more than one element: // we would never want to take remove 0 from our stack.
pop one element from stack
end while loop
insert i as child of node (stack - > top) in RL tree
push i into stack.
end for loop.
we will perform simple dfs on tree to perform simple euler tour (link to study) of trees and get store each node’s timer values, which we will use at the time of queries. as you could have figrured out only valid paths in the tree are from a parent node to its child nodes. there are no other routes. thus we just have to move downwards to perform queries.
we have constructed our tree and know how to use them till now. now we arrange our Values of nodes for the trees so that we can perform segment sum Queries and and single node value update query in our tree.
if we make a linear prefix sum array / vector for each tree this will help us to do sum Queries in O (1) time, but updates in O(q) time. and Q is <= 2 * 10^5. so O(q) would clearly not work here. we need something fast.
for this i couln’t find any other way than HLD (Heavy Light Decomposition).
HLD is made exactly to tacle problems like this to which we have arrived.
I can’t explain that topic here, here is a link to read about it.
and one youtube video’s link i found very helpful.
I’d prefer to read first and then jump to youtube video if you still unsure of how to do this.