Andsqr

My Soln

My Approach -

Similar to [TLE] SPOJ Matsum Help

I used 2D segment Tree + lazy propogation for range Updates and range Sum queries.

Instead of the 2d array, I used maps for storing values.

My idea Similar to Matsum I assumed N*N matrix with entries 0,1 where A[i][j] is 1 when and of (A_i ,... A_j) is a perfect square otherwise zero.

And answering queries directly follows answer range-sum query as in Matsum problem.

Editorial mentions 2 soln and both of them uses fenwick tree. But the editorial also mentions that this can be solved using segment tree + lazy propagation.