Offline algoritmi
Uvod
U nekim je zadacima s upitima potrebno rješavati upite jedan po jedan, onim redom kojim su zadani. Tada gradimo neku strukturu koja odgovara na upite u složenosti npr. ili . Naravno, te složenosti mogu biti i amortizirane ako nam to treba.
Često ne moramo ispisati odgovor na upit prije nego se unosi novi upit, i prethodni upiti ne utječu na stanje naše strukture za novi upit. Možemo reći da su svi upiti međusobno nezavisni i nebitan je redoslijed kojim na njih odgovaramo. Zato možemo poredati upite onako kako nama najviše odgovara, preprocesuirati ih sve odjednom, i ispisati odgovore u izvornom poretku.
Primjer
Riješimo sljedeći zadatak s Mo's algorithm / sqrt decomposition.
Trik je da izaberemo neki i podijelimo niz duljine na bucketa duljine (zadnji skratimo po potrebi). Zatim ćemo prvo riješiti sve upite kojima je lijevi indeks unutar bucketa, pa sve upite kojima je lijeva granica unutar bucketa, i tako sve do -tog bucketa. Unutar nekog bucketa pak rješavamo upite tako da sortiramo desnu granicu, a lijevu pomičemo po potrebi unutar bucketa. Naša će složenost biti , a može se dokazati da to poprima minimum za , te je složenost našeg rješenja .
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MaxN = 200005;
const int MaxA = 1000005;
const int BLOC = 450;
struct query{
int L, R;
int j; //indeks
ll res;
};
bool cmp(query X, query Y){
if (X.L / BLOC != Y.L / BLOC)
return X.L / BLOC < Y.L / BLOC;
return X.R < Y.R;
}
bool cmp_end(query X, query Y){
return X.j < Y.j;
}
query Q[MaxN];
int a[MaxN];
int c[MaxA];
int N, M;
ll add(int pos){
c[a[pos]]++;
return (ll)a[pos] * (2*c[a[pos]] - 1);
}
ll rem(int pos){
c[a[pos]]--;
return (ll)a[pos] * (2*c[a[pos]] + 1);
}
int main(){
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++){
scanf("%d", a+i);
}
int tL, tR;
for (int i = 0; i < M; i++){
scanf("%d%d", &tL, &tR);
Q[i].L = tL; Q[i].R = tR; Q[i].j = i;
}
sort(Q, Q + M, cmp);
int cL = 0, cR = 0;
ll ans = 0;
for (int i = 0; i < M; i++){
int L = Q[i].L;
int R = Q[i].R;
while (cL < L){
ans -= rem(cL);
cL++;
}
while (cL > L){
cL--;
ans += add(cL);
}
while (cR < R){
cR++;
ans += add(cR);
}
while (cR > R){
ans -= rem(cR);
cR--;
}
Q[i].res = ans;
}
sort(Q, Q + M, cmp_end);
for (int i = 0; i < M; i++)
cout<<Q[i].res<<endl;
return 0;
}