1. Totálny intervaláč vzorové riešenie

10 10
-5 -4 -3 -2 -1 0 1 2 3 4
1 0 4 1
1 5 9 1
2 0 9 3
3 0 9
4 0 9
3 0 1
4 2 3
3 4 5
4 6 7
3 8 9

-2
-2
-2
-2
0
1
1

Niekedy je riešenie úlohy jednoducho popísateľné, ale cesta k nemu nemusí byť vôbec intuitívna. Čitateľ môže nadobudnúť pri čítaní vzorového riešenia pocit, že to predsa nemôže fungovať, to nemôže byť dosť rýchle!

Toto je jedna z takých úloh. Aj preto veľkú časť návodu tvorí zdôvodnenie časovej zložitosti.

Všetky operácie okrem delenia (teda pripočítanie ku každému prvku v intervale, minimum na intervale, a súčet na intervale) zvládne obyčajný lazy-loading intervalový strom. Takisto zvláda aj operáciu maximum na intervale. Na čo by nám ale bola táto ďalšia operácia dobrá?

Pomocou nej budeme vedieť šikovne obísť delenie číslom \(d\): začneme vo vrchole reprezentujúcom celý interval. Označme minimum na intervale \(m\) a maximum \(M\). Ak platí \(\lfloor\frac{m}{d}\rfloor - m = \lfloor\frac{M}{d}\rfloor - M\), tak ku všetkým prvkom v intervale pripočítame \(\lfloor\frac{m}{d}\rfloor - m\) a končíme. V opačnom prípade zavoláme (túto) deliacu procedúru osobitne pre ľavého a pravého syna. (Je to teda akási hrubá sila s orezávaním.)

Dôkaz správnosti

Prečo si môžeme dovoliť v horeuvedenom prípade namiesto delenia pripočítavať \(\lfloor\frac{m}{d}\rfloor - m\)? Rozmyslite si, že ak platí predpoklad \(\lfloor\frac{m}{d}\rfloor - m = \lfloor\frac{M}{d}\rfloor - M\), tak musí platiť buď \(m = M\) alebo \(m + 1 = M\). Takže každý prvok v intervale má hodnotu buď \(m\), alebo \(M\). V oboch prípadoch je rozdiel spôsobený delením rovnaký (vďaka predpokladu).

Časová zložitosť

V podstate každá operácia delenia na intervale ho rozdelí na niekoľko podintervalov, a na každom z nich spravíme operáciu pripočítania (na rôznych intervaloch pripočítavame rôzne konštanty). Ukážeme, že dokopy týchto pripočítaní nemôže byť veľa.

Zamyslime sa nad tým, kedy môže na hranici medzi prvkami \(i\) a \(i + 1\) končiť podinterval. Prečo nás to zaujíma? Ak chceme vypočítať počet pripočítaní, ktorými daná operácia delenia prispela, tak je to počet podintervalov, a ten je rovný \(1 +\) počet hraníc podintervalov (nerátajúc začiatok celého intervalu ani jeho koniec).

Ak bol pred delením rozdiel prvkov \(i\) a \(i + 1\) v absolútnej hodnote rovný \(s\), tak po delení bude nanajvýš \(\lceil\frac{s}{2}\rceil\). Podinterval nám tam končí práve vtedy, keď sa tento rozdiel zmenšil.

Koľkokrát sa tento rozdiel môže takto zmenšiť? Ak neberieme do úvahy, že sa tento rozdiel môže zmeniť aj vtedy, keď dostaneme pripočítanie/delenie ovplyvňujúce iba jeden z prvkov \(i, i + 1\), tak sa môže zmenšiť najviac \(O(\log C)\)-krát, kde \(C = 10^9 + q \cdot 10^4\). (Na začiatku je rozdiel rádovo nanajvýš \(C\). Pretože sa pri každom delení rádovo spoloviční, môžeme ich mať len \(O(\log C)\). A nakoniec sa ešte raz môže zmenšiť z \(1\) na \(0\), ale to je len konštanta.)

Zoberme teraz do úvahy zmeny spôsobené operáciami, ktoré ovplyvňujú iba jeden z prvkov \(i, i + 1\). V najhoršom prípade nám rozdiel nastavia na nejaké číslo rádovo \(C\), a opäť ho budeme môcť znížiť \(O(\log C)\)-krát. Každá takáto operácia nám týmto spôsobom ovplyvní iba \(2\) rozdiely – na začiatku a na konci intervalu.

Môžeme sa na to teda pozerať takto: na začiatku máme pole čísel dĺžky \(n - 1\). Číslo na pozícii \(i\) hovorí, koľkokrát ešte môžeme zmenšiť rozdiel prvkov \(i\) a \(i + 1\). Na začiatku je pole vyplnené nejakými číslami od \(0\) po \(k\) (kde \(k\) je rádovo \(\log C\)). Ďalej budeme mať rádovo \(q\) krokov, a v každom kroku môžeme spraviť jedno z nasledovných:

• Nastavíme niektoré číslo na nejakú hodnotu od \(0\) po \(k\). (Toto reprezentuje zmenu rozdielu na okraji intervalu, v ktorom robíme operáciu.)
• Zoberieme si súvislý úsek, každé číslo v ňom väčšie ako \(1\) znížime o \(1\), a každé číslo rovné \(1\) môžeme znížiť na \(0\). K počítadlu pripočítame \(1\), a ďalších \(1\) za každé číslo v úseku, ktoré sme znížili. (Reprezentuje delenie na intervale.)

Na konci máme v počítadle počet pripočítaní, ktorými prispeli operácie delenia. Aká najväčšia hodnota teda môže byť v počítadle? Ak by sme krok prvého typu nemali povolený, tak by bola odpoveď rádovo \(nk + q\). Za každý krok prvého typu sa nám toto obmedzenie zvýši najviac o \(k\). Takže najväčšia možná hodnota počítadla je rádovo \(nk + qk + q\), čo je \(O((n + q) \log C)\).

Každé pripočítanie má časovú zložitosť \(O(\log n)\), a “normálnych” pripočítaní máme \(O(q)\). Dokopy tak dostávame časovú zložitosť \(O((n + q) \log C \log n)\).