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

題意：
給一個長度為 N 的數列 A[]。T 筆詢問，問對 [ L, R ] 中存在的所有相異數值 s，SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中，s 出現的次數。

資料規模：
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;
}