Arithmetic subtree DMOJ

Hi there!
I’m stuck on implementation of

I’ve been getting TLE with O(n + q * sqrt(n+q)*logn) and I don’t know how to improve it
Anyone knows a solution in just (n+q * sqrt(n+q))?
Or a code that hot AC?

Thanks in advance :slight_smile:

Could you actually show us your code (formatted and commented, preferably)?

Given that the updates/queries are basically 2 dimensional (one dimension is traversal index, another is height), it’s not clear how to do it any faster than O(q log(n)^2) with a 2D data structure. This should be about the same speed as O(q sqrt(n) log(n)), which I’m guessing is some kind of sqrt decomposition + data structure? So your solution probably just needs to be optimized.