MO's algorithms - D. Powerful array - Codeforces


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).


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 :slight_smile: … you help me grow.