Mike and OR tree problem

#1


How to optimise this code as I am getting TLE?

#2

@nayakashutosh99,
Complexity of your code is O(n^2), no amount t of optimisation would be enough. Try to do it in O(n)

#3

Can you give some hint to solve in O(n)?

#4

@nayakashutosh99,
Do you know sparse table, LCA and sqrt decomposition?

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

Sorry forgot to provide the feedback