I submitted the problem using segment trees but got 70 points only…then i saw the inherent pattern in the queries…that were being generated by the formulae…by the corresponding N values…
and came with a faster dp approach but still got 70 points…
finally i wrote a sparse table…for quering in O(1) …but still got 70 points…
people got AC using sparse table…where did i go wrong?
here is my solution http://www.codechef.com/viewsolution/6754646