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.