Help needed in problem STRAIGHT

I tried to solve this problem using query square root decomposition and I am not able to come with a techinique to perform updates in O(n) or O(nlogn) for each query blocks.

Can someone help me out with this part, I have gone throught the editorial and they are using FFT for that.

Do we have something simpler alternative for that?

Tanuj sir(@tanuj_khattar ) can you please look into it.


1 Like

Hey, I invested some time on it but couldn’t come up with something other than FFT i.e if we go for time-domain range-updates then that would give us a TLE, and there’s no way out (for me atleast).