Algoritmul lui Mo

Algoritmul lui Mo (Mo’s Algorithm) este o tehnică pentru a răspunde eficient la interogări offline pe intervale. Se bazează pe aceeași idee de blocuri de √n ca și Șmenul lui Batog, dar abordarea e diferită: în loc să precalculăm pe blocuri, sortăm inteligent interogările și menținem un răspuns curent pe care îl actualizăm incremental.

Complexitate: O((n + q) * √n).

Când folosim algoritmul lui Mo?

Avem un vector cu n elemente și q interogări de forma [st, dr]. Pentru fiecare, trebuie să calculăm ceva pe acel interval (numărare elemente distincte, frecvența maximă, sumă cu condiție, etc.).

Condiții:

• Nu avem actualizări pe vector (vectorul nu se modifică)
• Putem procesa interogările în orice ordine (offline)
• Putem adăuga și elimina un element din răspunsul curent în O(1) sau O(log n)

Ideea

Imaginează-ți că ai o fereastră [curSt, curDr] pe vector și cunoști răspunsul pentru ea. Poți extinde sau micșora fereastra cu câte un element la fiecare pas:

• Adaugă element la dreapta: curDr++
• Adaugă element la stânga: curSt--
• Elimină element din dreapta: curDr--
• Elimină element din stânga: curSt++

Dacă procesăm interogările într-o ordine aleatoare, fereastra se mișcă mult. Dar dacă le sortăm inteligent, minimizăm numărul total de mișcări.

Sortarea interogărilor

Împărțim pozițiile în blocuri de √n. Sortăm interogările astfel:

1. Primar: după blocul lui st (blocul = st / B)
2. Secundar: după dr (crescător)

B = 3, interogări: [1,5], [2,8], [4,7], [1,3], [5,9], [3,6]

Bloc 0 (st=1..3): [1,3], [1,5], [2,8], [3,6]  ← sortate după dr
Bloc 1 (st=4..6): [4,7], [5,9]                  ← sortate după dr

Interogările cu st în același bloc sunt grupate, iar dr crește monoton în cadrul grupului. Asta face ca curDr să se miște cel mult n pași per bloc, iar curSt cel mult B pași per interogare.

Complexitate

• Avem n / B blocuri
• curDr parcurge cel mult n pași per bloc → total n * (n/B) = n * √n
• curSt se mișcă cel mult B pași per interogare → total q * B = q * √n
• Total: O((n + q) * √n)

Problema clasică: numărul de elemente distincte pe interval

Avem un vector cu n elemente și q interogări [st, dr]. Pentru fiecare, câte valori distincte sunt pe acel interval?

Exemplu

Vector: 1 2 1 3 2 1 4 1
Interogări:
  [1, 4] → valorile: 1, 2, 1, 3 → distincte: {1, 2, 3} → 3
  [3, 7] → valorile: 1, 3, 2, 1, 4 → distincte: {1, 2, 3, 4} → 4
  [5, 8] → valorile: 2, 1, 4, 1 → distincte: {1, 2, 4} → 3

Codul complet

#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int fr[100001];
int rez[100001];
int n, q, B;
int distincte = 0;

struct Query {
    int st, dr, idx;
};

Query qr[100001];

bool cmp(Query a, Query b) {
    int blocA = a.st / B;
    int blocB = b.st / B;
    if (blocA != blocB)
        return blocA < blocB;
    return a.dr < b.dr;
}

void adauga(int poz) {
    fr[v[poz]]++;
    if (fr[v[poz]] == 1)
        distincte++;
}

void elimina(int poz) {
    fr[v[poz]]--;
    if (fr[v[poz]] == 0)
        distincte--;
}

int main()
{
    fin >> n >> q;
    B = max(1, (int)sqrt(n));

    for (int i = 1; i <= n; i++)
        fin >> v[i];

    for (int i = 0; i < q; i++) {
        fin >> qr[i].st >> qr[i].dr;
        qr[i].idx = i;
    }

    sort(qr, qr + q, cmp);

    int curSt = 1, curDr = 0;

    for (int i = 0; i < q; i++) {
        int st = qr[i].st;
        int dr = qr[i].dr;

        while (curDr < dr) adauga(++curDr);
        while (curDr > dr) elimina(curDr--);
        while (curSt < st) elimina(curSt++);
        while (curSt > st) adauga(--curSt);

        rez[qr[i].idx] = distincte;
    }

    for (int i = 0; i < q; i++)
        fout << rez[i] << "\n";

    return 0;
}

date.in:

8 3
1 2 1 3 2 1 4 1
1 4
3 7
5 8

date.out:

3
4
3

Pas cu pas

Vector: 1 2 1 3 2 1 4 1, B = 2

Interogări sortate (bloc lui st, apoi dr): - [1, 4] (bloc 0, dr=4) - [3, 7] (bloc 1, dr=7) - [5, 8] (bloc 2, dr=8)

Interogarea 1: [1, 4]

Fereastra: curSt=1, curDr=0 (goală)

Răspuns: 3

Interogarea 2: [3, 7]

Fereastra curentă: [1, 4], trebuie [3, 7]

Răspuns: 4

Interogarea 3: [5, 8]

Fereastra curentă: [3, 7], trebuie [5, 8]

Răspuns: 3

Total: 12 operații. Fără Mo (brute force): 4+5+4 = 13. Diferența crește masiv pe input-uri mari.

Structura generală

Algoritmul lui Mo urmează mereu aceeași structură:

1. Citim vectorul și interogările
2. Alegem B = √n
3. Sortăm interogările (bloc st, apoi dr)
4. Pornim cu fereastra goală [curSt=1, curDr=0]
5. Pentru fiecare interogare:
   a. Extindem/micșorăm fereastra cu adauga/elimina
   b. Salvăm răspunsul pe poziția originală
6. Afișăm răspunsurile în ordinea originală

Ce se schimbă de la problemă la problemă sunt funcțiile adauga și elimina.

Alt exemplu: suma valorilor distincte pe interval

Schimbăm doar adauga și elimina:

long long sumaDistincte = 0;

void adauga(int poz) {
    fr[v[poz]]++;
    if (fr[v[poz]] == 1)
        sumaDistincte += v[poz];
}

void elimina(int poz) {
    fr[v[poz]]--;
    if (fr[v[poz]] == 0)
        sumaDistincte -= v[poz];
}

Restul codului rămâne identic.

Alt exemplu: frecvența maximă pe interval

int frMax = 0;
int cntFr[100001]; // cntFr[f] = câte valori au frecvența f

void adauga(int poz) {
    cntFr[fr[v[poz]]]--;
    fr[v[poz]]++;
    cntFr[fr[v[poz]]]++;
    if (fr[v[poz]] > frMax)
        frMax = fr[v[poz]];
}

void elimina(int poz) {
    cntFr[fr[v[poz]]]--;
    if (fr[v[poz]] == frMax && cntFr[fr[v[poz]]] == 0)
        frMax--;
    fr[v[poz]]--;
    cntFr[fr[v[poz]]]++;
}

Optimizare: ordinea alternantă

O îmbunătățire practică: pentru blocuri impare, sortăm dr descrescător în loc de crescător. Asta face ca curDr să “meargă și să vină” în loc să se reseteze la fiecare bloc.

bool cmp(Query a, Query b) {
    int blocA = a.st / B;
    int blocB = b.st / B;
    if (blocA != blocB)
        return blocA < blocB;
    if (blocA % 2 == 0)
        return a.dr < b.dr;
    return a.dr > b.dr;
}

În practică, reduce timpul cu 20-40%.

Când NU funcționează Mo?

• Cu actualizări pe vector (vectorul se modifică între interogări). Există varianta “Mo with updates” dar e mult mai complexă.
• Online - când trebuie să răspunzi la fiecare interogare înainte de a o citi pe următoarea.
• Când adauga/elimina nu se pot face eficient (O(1) sau O(log n)).

Comparație

Mo e ideal pentru probleme fără actualizări unde informația pe interval e greu de combinat (elemente distincte, frecvențe).

Greșeli frecvente

1. Uitarea salvării indexului original

qr[i].idx = i; // ESENȚIAL - altfel nu știm ordinea de afișare

Sortăm interogările, dar răspunsurile trebuie afișate în ordinea originală.

2. Ordinea operațiilor la extindere/micșorare

// CORECT:
while (curDr < dr) adauga(++curDr);
while (curDr > dr) elimina(curDr--);
while (curSt < st) elimina(curSt++);
while (curSt > st) adauga(--curSt);

Ordinea contează: extindem mai întâi, apoi micșorăm. Altfel putem avea fereastra goală momentan.

3. Vectorul de frecvențe nu e resetat

Frecvențele pornesc de la 0. Dacă reutilizăm vectorul fără resetare, rezultatele sunt greșite.

4. B prea mic sau prea mare

B = max(1, (int)sqrt(n)); // CORECT

Dacă B = 0, avem împărțire la zero. Dacă B = 1, complexitatea degenerează.

Ce să reții

• Mo’s Algorithm sortează interogările offline pentru a minimiza mișcările ferestrei.
• Sortare: primar după blocul lui st, secundar după dr.
• Complexitate: O((n + q) * √n).
• Schimbăm doar adauga/elimina de la problemă la problemă.
• Funcționează fără actualizări pe vector.
• Salvăm indexul original pentru a afișa răspunsurile în ordine.
• Optimizare: ordinea alternantă a lui dr pe blocuri impare.