# CFR 86 D. Powerful array ( Mo's Algorithm, Math )

Problem - D - Codeforces

First line contains two integers n and t (1 ≤ n, t ≤ 200000) — the array length and the number of queries correspondingly.
Second line contains n positive integers ai (1 ≤ ai ≤ 1e6) — the elements of the array.
Next t lines contain two positive integers l, r (1 ≤ l ≤ r ≤ n) each — the indices of the left and the right ends of the corresponding subarray.

( ( K[ s ] + 1 )^2 - ( K[ s ] ) ) * s = ( 2 * K[ s ] + 1 ) * s

O( N^1.5 + T^1.5 ) / O( N + T )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = ( int ) 2e5;
const int MAXT = ( int ) 2e5;
const int MAXA = ( int ) 1e6;
const int BLK = 500;

int N, T;
int A[ MAXN ];
int L[ MAXT ], R[ MAXT ];
int qord[ MAXT ];

int K[ MAXA + 1 ];
long long ans[ MAXT ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N >> T;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
for( int i = 0; i < T; ++i ){
cin >> L[ i ] >> R[ i ];
--L[ i ]; // [ L, R )
qord[ i ] = i;
}
sort( qord, qord + T, [ & ]( int i, int j ){
if( L[ i ] / BLK != L[ j ] / BLK ) return L[ i ] / BLK < L[ j ] / BLK;
return R[ i ] < R[ j ]; } );
for( int ti = 0, lb = 0, rb = 0; ti < T; ++ti ){ // [ lb, rb )
static long long cur = 0;
while( L[ qord[ ti ] ] < lb ){
--lb;
cur += ( 2LL * K[ A[ lb ] ] + 1 ) * A[ lb ];
++K[ A[ lb ] ];
}
while( lb < L[ qord[ ti ] ] ){
cur -= ( 2LL * ( K[ A[ lb ] ] - 1 ) + 1 ) * A[ lb ];
--K[ A[ lb ] ];
++lb;
}
while( R[ qord[ ti ] ] < rb ){
--rb;
cur -= ( 2LL * ( K[ A[ rb ] ] - 1 ) + 1 ) * A[ rb ];
--K[ A[ rb ] ];
}
while( rb < R[ qord[ ti ] ] ){
cur += ( 2LL * K[ A[ rb ] ] + 1 ) * A[ rb ];
++K[ A[ rb ] ];
++rb;
}
ans[ qord[ ti ] ] = cur;
}
for( int i = 0; i < T; ++i ){
cout << ans[ i ] << "\n";
}
return 0;
}
```