Ruutjuurelised võtted

"Ruutjuureliseks võtteks" võib nimetada misiganes algoritmi, kus ruutjuur kuidagi figureerib. Programmeerimisvõistlustel on ilmnenud mõned ruutjuure algoritmis kasutamise tüüpilisemad mustrid. Käesolevas materjalis proovime näidete abil neid mustreid näidete varal selgitada, et lugeja suudaks tulevikus ülesannetele selliseid lahendusi välja mõelda.

Massiivi tükeldamine

Massiivi alalõikude summa

Järgmist ülesannet on kindlasti paljud lugejad juba lahendanud ja oskavad lahendada ka keerukusega, mis on parem, kui $O(q \sqrt{n})$. Kuna see on aga kõige lihtsam seda tüüpi ülesanne, siis toome illustratiivsuse mõttes siiski lahenduse välja.

Olgu antud massiiv $A$ pikkusega $n$, kus alguses on kõik elemendid nullid. On $q$ päringut, kaht tüüpi:

Antud $i$ ja $v$. Lisa $A[i]$ väärtusele $v$.
Antud $l$ ja $r$. Leia $A[l] + A[l + 1] + \cdots + A[r]$.

$1 \le n, q \le 10^5$.

Jagame massiivi blokkideks suurusega $B$. Igas blokis hoiame meeles selle bloki elementide summa. Päringute täitmine näeb siis välja nii:

Kui tuleb esimene päring, siis liidame $A[i]$ väärtusele $v$ ja vastava bloki väärtusele samuti $v$.
Kui tuleb teist tüüpi päring, siis liidame vastusele kõik blokid, mis on täielikult vahemiku $l \ldots r$ sees. Seejärel liidame vastusele need elemendid, mis on vahemiku sees, mille blokid aga mitte.

Iga esimest tüüpi päringu täitmine võtab alati $O(1)$ aega. Teist tüüpi päringu korral on meil vaja läbi käia ülimalt $O(\frac{n}{B})$ blokki ja ülimalt $O(B)$ blokivälist elementi. Kokku on iga päringu täitmise keerukus $O(\frac{n}{B} + B)$. See tuleb kõige väikesem, kui võtta $B = \sqrt{n}$. Siis on kogu lahenduse keerukus $O(q \sqrt{B})$.

Vastikumad arvutused massiivi alamlõikudel

Järgmises ülesandes on eelmisest mõnevõrra keerukamad päringud. Ka seda ülesannet on võimalik lahendada parema keerukusega, kui $O(q \sqrt{n})$, aga see lahendus muutuks päris keeruliseks; tõenäoliselt on ruutjuureline lahendus lihtsam.

On antud massiv $A$ pikkusega $n$, kus alguses on kõik elemendid nullid. On $q$ päringut, nelja tüüpi:

Antud $l$ ja $r$. Asendame kõik elemendid $A[l], A[l + 1], \ldots, A[r]$ ühtedega.
Antud $l$ ja $r$. Asendame kõik elemendid $A[l], A[l + 1], \ldots, A[r]$ nullidega.
Antud $l$ ja $r$. Asendame elementide $A[l], \ldots, A[r]$ seas kõik ühed nullidega ja vastupidi.
Antud $l$ ja $r$. Leia vähim $i$ nii, et $l \le i \le r$ ja $A[i] = 0$.

$1 \le n, q \le 10^5$.

Lahenduse üldskeem on sarnane. Kui meil on antud vahemik $l \ldots r$ (ükskõik, mis päringu korral), uuendame iga vahemikku täielikult kuuluvat blokki $O(1)$ ajas ja seejärel elemente, mis on vahemiku sees, mille blokid aga mitte.

Selleks peaksime meeles hoidma iga bloki kohta järgmisi asju:

Kas blokis on kõik elemendid nullideks tehtud?
Kas blokis on kõik elemendid ümber pööratud?

Lisaks hoiame meeles $A[i]$ väärtust iga $i$ korral kahe erandiga:

Kui oleme märkinud, et mingis blokis on kõik elemendid nullitud, siis kohtleme $A[i]$ kui nulli sõltumata sinna tegelikult kirjutatud arvust.
Kui oleme märkinud, et mingis blokis on kõik elemendid pööratud, siis kohtleme $A[i]$ kui tema pöördväärtust.

Augud

Reas on $n$ auku, nummerdatud $1 \ldots n$. Iga auku iseloomustab tema "jõud" ehk arv $A[k]$. Kui pall satub auku $k$, põrkab ta otsekohe edasi auku $k + A[k]$. Kui sellise numbriga auku pole, väljub pall reast. On $q$ päringut, kaht tüüpi:

Antud $k$ ja $x$. Sea augu number $k$ jõuks $x$.
Antud $k$. Viska pall auku number $k$ ja väljasta, mis on viimane auk, mida pall külastab enne reast väljumist.

$1 \le n, q \le 10^5$.

Sarnaselt eelmistele jagame aukude rea blokkideks suurusega $\sqrt{n}$. Iga augu $k$ kohta hoiame meeles kaks järgmist auku:

See, kuhu pall august $k$ järgmiseks põrkab.
Esimene auk, kuhu pall august $k$ jõuab, mis ei ole selle auguga samas blokis.

Nüüd tuleb läbi mõelda, kuidas seda informatsiooni teist tüüpi päringutele vastamiseks kasutada ja kuidas seda informatsiooni esimest tüüpi päringute korral kiirest uuendada.

"Suurte" ja "väikeste" asjade eraldi töötlemine

Kommide söömine

On kaht sorti komme: sinised ja punased.

Iga sinine komm kaalub $w_b$ grammi ja annab $h_b$ punkti.
Iga punane komm kaalub $w_r$ grammi ja annab $h_r$ punkti.

Mis on maksimaalne punktide arv, kui me võime ära süüa ülimalt $c$ grammi komme? $1 \le w_b, w_r, h_b, h_r, c \le 10^9$.

Vaatleme eraldi kaht juhtu:

Leidub mingi komm, mille kaal on suurem, kui $\sqrt{c}$. Kui näiteks siniste kommide kaal on suurem, kui $\sqrt{c}$, siis me siniseid komme ei saa rohkem, kui $\sqrt{c}$ tükki süüa. Siis võimegi kõik erinevad siniste kommide arvud läbi käia ja vaadata, milline annab parima tulemuse.
Mõlema kommi kaal on väikesem, kui $\sqrt{c}$. Oletame üldisust kitsendamata, et $\frac{h_b}{w_b} \le \frac{h_r}{w_r}$. Saab näidata, et meil ei ole mõtet süüa rohkem, kui $w_r$ sinist kommi. See tähendab jälle, et siniseid komme ei saa rohkem kui $\sqrt{c}$ tükki süüa.

Keerukus on $O(\sqrt{c})$.

Hulkade ühisosad

On antud $n$ hulka $A_1, A_2, \ldots, A_n$. Kas leiduvad kaks hulka $A_i$ ja $A_j$ nii, et hulkadel $A_i$ ja $A_j$ on vähemalt kaks ühist elementi?
Hulkade elementide summa on $S$, kus $S \le 2 \cdot 10^5$.

Jaotame hulgad "suurteks" ja "väikesteks": hulk on suur, kui temas on vähemalt $\sqrt{S}$ elementi. Muuhulgas võib tähele panna, et suuri hulki on ülimalt $\sqrt{S}$ tükki. Nüüd tuleb leiutada kolm erinevat algoritmi, mis kontrollivad järgmisi asju:

Kas leiduvad kaks suurt hulka, millel on vähemalt kaks ühist elementi?
Kas leiduvad kaks väikest hulka, millel on vähemalt kaks ühist elementi?
Kas leiduvad suur ja väike hulk, millel on vähemalt kaks ühist elementi?

Mo algoritm

Unikaalsete elementide loendamine

On antud massiiv $A$ pikkusega $n$, mis koosneb arvudest $A[1], A[2], \ldots, A[n]$, mis kõik on vahemikus $1 \ldots 10^5$. Meile antakse $q$ päringut kujul:

Antakse arvud $l$ ja $r$. Arvutada, mitu erinevat arvu on arvude $A[l], A[l + 1], \ldots, A[r]$ seas.

$1 \le n, q \le 10^5$.

Seejuures on oluline märkida, et meile antakse kõik päringud korraga kätte. See tähendab, et me ei pea päringutele vastama samas järjekorras, milles nad meile antakse. Võime neid ümber järjestada kuidas soovime, pärast paneme algsesse järjekorda tagasi. Mo algoritm põhinebki sellel, et üks teatud "naiivne" algoritm muutub väga kiireks, kui päringud on "heas" järjekorras.

"Algoritm otspunktide nihutamisega"

Vaatleme igal hetkel ühte vahemikku meie massiivis; teises massiivis hoiame iga arvu kohta meeles, mitu tükki seda arvu vahemikus on. Vahemiku otspunkte ühe võrra ``nihutades'' liigume päringult päringule.

Kui massiiv on $[3, 5, 5, 6, 5, 2, 3]$ ja päringud on $(2, 5)$, $(3, 7)$ ning $(1, 4)$, siis võib algoritm välja näha midagi sellist:

"Loendamismassiivi" ja vastust saame uuendada iga nihutuse järel keerukusega $O(1)$.

See algoritm ise aga väga hea veel ei ole. Võib ju olla, et iga kahe päringu vahel tuleb nihutada mõlemat pointerit peaaegu $n$ sammu. Nii et halvimal juhul on keerukuseks lausa $O(nq)$. Et $nq$ võib olla kuni $10^{10}$, on algoritm liiga aeglane. Järgmine samm on järjestada päringud ümber kavalal moel nii, et see algoritm muutuks mitu suurusjärku kiiremaks.

Mo järjestus

Järjestame päringud ümber järgmisel moel. Kõigepealt jaotame päringud "blokkidesse":

esimesse blokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $1 \ldots \sqrt{n}$;
teise blokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $\sqrt{n} \ldots 2 \sqrt{n}$;
kolmandasse blokki lähevad need päringud, mille vasakpoolsed otspunktid jäävad vahemikku $2 \sqrt{n} \ldots 3 \sqrt{n}$;
jne.

Nii jaotuvad päringud $\approx \sqrt{n}$ blokki.

Pärast blokkidesse jaotamist sorteerime igas blokis päringud ära parempoolse otspunkti järgi.

Võrdlejafunktsioonid

Mugav viis Mo algoritmi implementeerida on kasutada nn võrdlejafunktsioone. Oletame, et oleme C++ keeles lugenud sisse päringud ja tahame nad Mo järjestusse panna. Näiteks on meil olemasolev kood midagi niisugust:

struct Query {
  int l, r, id;     
};

int main () {
  int n, q;
  cin >> n >> q;

  vector<Query> queries;
  for (int i = 0; i < q; i++) {
    cin >> queries[i].l >> queries[i].r;
    queries[i].id = i;
  }
}

Tahaksime, et saaksime selle päringute vektori panna Mo järjestusse lihtsalt sisseehitatud sorteerimismeetodi abil. Selleks implementeerime funktsiooni comp_mo, mis võtab sisse kaks päringut $p$ ja $q$. Funktsioon peab tagastama true, kui päring $p$ peab tulema järjekorras enne päringut $q$. Üks võimalik implementatsioon on järgmine:

bool comp_mo (Query p, Query q) {
  if (p.l / BLOCK_SIZE != q.l / BLOCK_SIZE) { // kui p ja q kuuluvad erinevatesse blokkidesse
    return p.l / BLOCK_SIZE < q.l / BLOCK_SIZE; // tagastame true, kui p kuulub väikesemasse
  }
  return p.r < q.r; // vastasel juhul sorteerime parempoolse otspunkti järgi
}

Nüüd võime päringute vektori sorteerida sisseehitatud funktsiooni sort abil.

sort(queries.begin(), queries.end(), comp_mo);

Keerukus

Kujutame nüüd ette, et me panime päringud ümber Mo järjestusse ja jooksutame oma otspunktide nihutamise algoritmi selle peal. Paneme tähele, et:

vasakpoolne pointer liigub kahe päringu vahel kõige rohkem $2 \sqrt{n}$ sammu, kokku ei tee ta rohkem, kui $O(q \sqrt{n})$.
parempoolne pointer liigub $\sqrt{n}$ korda vasakult paremale ja tagasi, kokku teeb $O(n \sqrt{n})$ sammu.

Seega keerukus on $O((q + n) \sqrt{n})$. Kui $n = q = 10^5$, siis $$(q + n) \sqrt{n} = (10^5 + 10^5) \sqrt{10^5} \approx 6.32 \cdot 10^7,$$ mis on piisavalt kiire.

Ja see võimaldabki meil ülesande ära lahendada! Kokkuvõttes:

loeme sisendi sisse ja paneme päringud ümber Mo järjestusse;
kasutame oma otspunktide nihutamisega algoritmi, et saada teada kõigi päringute vastused;
prindime päringute vastused (esialgses järjestuses!) välja.

Massiivi võimsus

Mo algoritmi saab sageli rakendada ülesannetes, kus on antud päringud, millel on vasak- ja parempoolne otspunkt. Meil piisab vaid kirjeldada otspunktide nihutamisega algoritmi. Siinkohal üks näide.

On antud massiiv $A$ pikkusega $n$. Kõik massiivi elemendid on vahemikust $1 \ldots 10^6$.
Vaatleme selle mingit alammassiivi $A[l], A[l + 1], \ldots, A[r]$. Defineerime alammassiivi $l \ldots r$ võimsuse järgnevalt. Iga $i$ korral tähistagu $K_i$ arvu $i$ esinemiste arvu selles alammassiivis. Alammassiivi $l \ldots r$ võimus arvutatakse siis valemiga $$ 1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + 10^6 \cdot K_{10^6}^2.$$ Meile antakse $q$ päringut kujul:

Antud $l$ ja $r$. Leia alammassiivi $l \ldots r$ võimsus.

Vastata kõikidele päringutele. $1 \le n, q \le 10^5$.

Piisab sellest, kui kirjeldame otspunktide nihutamisega algoritmi.

Hoiame meeles mingi vahemiku võimsust ja seda, kui palju on antud vahemikus iga arvu. Hakkame otspunkte nihutama. Kujutame ette, et vahemikku lisandub arv $i$. Enne lisandumist oli vahemiku võimsus $$1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + i \cdot (K_i - 1)^2 + \cdots + 10^6 \cdot K_{10^6}^2.$$ Pärast on võimsus $$1 \cdot K_1^2 + 2 \cdot K_2^2 + \cdots + i \cdot K_i^2 + \cdots + 10^6 \cdot K_{10^6}^2.$$ Võimsuse muut on $$iK_i^2 - i(K_i - 1)^2= 2i K_i - i.$$ Analoogilise valemi võime tuletada ka siis, kui vahemikust eemaldub arv $i$. Sellest teadmisest piisab, et lahendada ülesanne Mo algoritmi abil.