Problem:-
Editorial :-
Problem Statement :-
Given an array a_{1}, a_{2}, ... a_{n}, and q queries to find \sum_{l}^{r}k_{i} * k_{i} * s_{i}, in the range l to r for which k is the frequency of s_{i} and s_{i} being unique integer and we do this for only unique numbers in the queried sub array. For example, when the elements in the range l to r are suppose, say 5 and only 3 being unique in them…we do above operation for only those 3 of the 5 elements.
Please correct me if I understood the problem in a different way than expected (After spending a lot of time, brainstorming, nightouts, I lost confidence in my problem understanding skills lately T_T).
Doubt:-
In the official editorial and even in the AC submissions, they’ve calculated the sqrt(n) to divide the given input array “a” right?, which is inherited from traditional sqrt-decomposition algorithm to divide it into “sqrt(n)” blocks so that it contains calculated info like cumulative sum or something like this right ?!
a_1+a_2 .. a_{sqrt(n)} => block_{0}
a_{sqrt(n)+1}+a_{sqrt(n)+2} .. a_{2*sqrt(n)} => block_{1}
a_{2*sqrt(n)+1}+a_{2*sqrt(n)+2} .. a_{3*sqrt(n)} => block_{2}
.
.
.
So that we don’t always have to traverse through n instead just sqrt(n) atmost for any certain offline or online query isn’t.
Finally, coming to doubt, I haven’t noticed people using frequency table for these blocks, all they computed was just like mentioned in the editorial, that is to sort the queries (MO’s algo) and move l and r accordingly. Actually editorial did mention to divide the array into “sqrt(n)” parts but never mentioned about maintaining “sqrt(n)” frequency tables for each of the decomposed block…even in the code I didn’t see them implementing those many frequency tables.
Thanks for your time 
… you help me grow.