Algoritmo di Mo per calcolare "potenza" dell'array

Question

Recentemente, ho appreso Mo's algorithm per la scomposizione quadrata delle query al fine di accelerare le soluzioni a determinati problemi.

Per praticare l'implementazione, ho cercato di risolvere D. Powerful array (un problema di contest passato su Codeforces) utilizzando questa idea. Il problema è il seguente:

Si dispone di un array con numeri interi .

Prendere in considerazione un sottoarray arbitrario . Definire come il numero di occorrenze di un numero intero in questo sottoarray. Il potere di un sottoarray è definito come la somma di per tutti gli interi (notare che c'è solo un numero positivo di termini per i quali questo non è zero).

rispondere alle domande . In ogni query, dati due numeri interi e , calcolare la potenza di .

Contiene:

utilizzando l'algoritmo di Mo, ho scritto il codice che risolve questo problema non in linea in . Sono sicuro che questo problema può essere risolto utilizzando questo algoritmo e la complessità del tempo, poiché ho ispezionato il codice accettato da altri e usano anche un algoritmo simile.

Il mio codice, tuttavia, gets a time limit exceeded verdict.

Di seguito è il codice che ho scritto:

#include <ios> 
#include <iostream> 
#include <cmath> 
#include <algorithm> 
#include <vector> 
#include <utility> 
#include <map> 

int sqt; 
long long int ans = 0; 
long long int arr[200005] = {}; 
long long int cnt[1000005] = {}; 
long long int tans[200005] = {}; 

struct el 
{ 
    int l, r, in; 
}; 

bool cmp(const el &x, const el &y) 
{ 
    if (x.l/sqt != y.l/sqt) 
     return x.l/sqt < y.l/sqt; 
    return x.r < y.r; 
} 

el qr[200005]; 

int main() 
{ 
    std::ios_base::sync_with_stdio(false); 
    std::cin.tie(NULL); 
    std::cout.tie(NULL); 
    int n, q, a, b; 
    std::cin >> n >> q; 
    sqt = sqrt((double)(n))+27; 
    for (int i = 0; i < n; i++) 
     std::cin >> arr[i]; 
    for (int i = 0; i < q; i++) 
    { 
     std::cin >> a >> b; 
     a--; b--; 
     qr[i].l = a; 
     qr[i].r = b; 
     qr[i].in = i; 
    } 
    std::sort(qr, qr+q, cmp); 

    int li = 0; //left iterator 
    int ri = 0; //right iterator 
    ans = arr[0]; 
    cnt[arr[0]]++; 

    for (int i = 0; i < q; i++) 
    { 
     while (li < qr[i].l) 
     { 
      ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
      cnt[arr[li]]--; 
      ans += cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
      li++; 
     } 
     while (li > qr[i].l) 
     { 
      li--; 
      ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
      cnt[arr[li]]++; 
      ans += cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
     } 
     while (ri < qr[i].r) 
     { 
      ri++; 
      ans -= cnt[arr[ri]]*cnt[arr[ri]]*arr[ri]; 
      cnt[arr[ri]]++; 
      ans += cnt[arr[ri]]*cnt[arr[ri]]*arr[ri]; 
     } 
     while (ri > qr[i].r) 
     { 
      ans -= cnt[arr[ri]]*cnt[arr[ri]]*arr[ri]; 
      cnt[arr[ri]]--; 
      ans += cnt[arr[ri]]*cnt[arr[ri]]*arr[ri]; 
      ri--; 
     } 
     tans[qr[i].in] = ans; 
    } 
    for (int i = 0; i < q; i++) 
     std::cout << tans[i] << '\n'; 
} 

si può suggerire qualsiasi (anche una o forse asintotico) il miglioramento non asintotico in grado di accelerare il programma abbastanza per passare il limite di tempo?

ho già provato le seguenti cose, inutilmente:

1. Utilizzando un vettore invece che una matrice.
2. Utilizzo di due coppie nidificate anziché struct.
3. Utilizzare solo una coppia e quindi utilizzare una mappa per provare a ripristinare l'ordine corretto di risposte.
4. Aggiunta di alcune varie costanti a sqt (come nel codice sopra).
5. Sovraccarico dell'operatore di confronto < all'interno della struttura el.

Mi sento come se mi mancasse qualcosa di importante, dal momento che gli altri codici che ho ispezionato sembrano passare il limite di tempo con un po 'di margine di manovra (circa mezzo secondo). Tuttavia, sembrano utilizzare lo stesso algoritmo del mio codice.

Qualsiasi aiuto sarebbe molto apprezzato!

Answer 1

Si potrebbe forza-ridurre

while (li < qr[i].l) 
    { 
     ans -= cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
     cnt[arr[li]]--; 
     ans += cnt[arr[li]]*cnt[arr[li]]*arr[li]; 
     li++; 
    } 

a

while (li < qr[i].l) 
    { 
     ans -= (2*cnt[arr[li]]-1)*arr[li]; 
     cnt[arr[li]]--; 
     li++; 
    } 

e allo stesso modo per gli altri.