De ce contează?
Ești bibliotecar și primești un teanc de comenzi: „adu-mi toate cărțile dintre
raftul l și raftul r". Dacă le rezolvi în ordinea în care au venit, alergi
de la un capăt al bibliotecii la celălalt după fiecare comandă. Un bibliotecar
isteț face altceva: rearanjează comenzile astfel încât fiecare să fie aproape
de precedenta — și atunci merge mereu doar câțiva pași între rafturi. Cărțile nu
se mută, doar ordinea comenzilor. Exact asta face algoritmul lui Mo cu
interogările pe intervale.
Intuiția
Ai un șir fix și q interogări de forma „pe intervalul [l, r], cât face …?"
(câte valori distincte, suma, câte perechi egale). Ține minte o fereastră
„curentă" [curL, curR] și răspunsul ei. Ca să treci la interogarea următoare,
muți capetele pas cu pas — adaugi sau scoți câte un element. De la Square Root
Decomposition împrumuți doar tăierea în blocuri de radical(n), dar nu pentru șir,
ci pentru a decide ordinea interogărilor.
Declicul are două jumătăți. Unu: răspunzi offline — știi toate interogările
dinainte, deci ai voie să le reordonezi. Doi: mutarea unui capăt cu un singur
pas e ieftină (un add sau un remove, ambele O(1)). Sortând interogările
pe blocuri de radical(n), ferestrele succesive diferă puțin, iar drumul total al
capetelor scade de la O(n*q) la O((n+q)*radical(n)).