8. Akademické zbrane vzorové riešenie

3
1 2
0 1
3 5
4
q 1 2
q 2 3
u 2 0 2
q 2 3

3
5
7

Tretia podúloha

Pozrime sa najprv na tretiu podúlohu – teda verziu úlohy, kde \(a_i\) je vždy \(0\). Simulujme si jednu q query a pozerajme sa na najvyšší bit výsledku. Ak tento bit nie je nastavený v žiadnom \(b_i\) v intervale, určite to musí byť \(0\). Ak je zapnutý v jednom \(b_i\), určite to chceme takto ponechať, inak by sme si výsledok určite zhoršili. Ten najzaujímavejší prípad ale nastáva, ak je zapnutý vo viacerých. Tu totiž môžeme pre jedno vybrať samotné \(b_i\) a pre druhé také číslo, ktoré má tento bit vypnutý, ale všetky nižšie zapnuté.

Teda napríklad keď v našom intervale nájdeme \(b_1 = 10 = 1010_2\) a \(b_2 = 9 = 1001_2\), tak si pre prvú pozíciu môžeme vybrať samotné \(b_1 = 1010_2\) a pre druhú \(0111_2\). Ich OR potom bude \(1111_2\), čo je evidentne optimálne.

Teda už máme nejaké riešenie tretej podúlohy – pre každú q query si postupne prechádzame bitmi odpovede od najvyššieho, nastavujeme ich podľa toho, či niekde existuje príslušný bit v \(b_i\) a keď také dokonca existujú viaceré, tak zvyšok bitov doplníme jednotkami. u query vyriešime triviálne – proste si prepíšeme dané \(b_i\).

Toto riešenie má ale časovú zložitosť \(O(q n \log A)\), kde \(A\) je najväčšie číslo v poli \(b_i\). Toto je ale príliš pomalé na vyriešenie tretej sady.

Zrýchlenie riešenia

Môžeme si všimnúť dve možné miesta na optimalizáciu – zahodiť zo zložitosti logaritmus alebo dokonca zahodiť celé \(n\).

Ak chceme zahodiť logaritmus, môžeme si všimnúť, že celé čo robíme je bitový OR všetkých \(b_i\) v intervale. To vieme urobiť triviálne lineárne. A teda okrem toho zisťujeme najvyšší bit, ktorý je zapnutý aspoň v dvoch číslach. Toto sa tiež dá efektívne urobiť troškou bitovej mágie. Už máme premennú \(O\), ktorá si udržiava OR všetkých zatiaľ spracovaných čísel. Zadefinujme si okrem toho \(D\). To vždy pri spracovaní prvku \(b_i\) updateneme na \(D \operatorname{OR} (O \operatorname{AND} b_i)\). Teda do neho vždy pridáme bity, ktoré sme už niekedy predtým videli ale aj sú nastavené v aktuálnom čísle, čo je presne čo chceme. Teda nakoniec si v \(D\) nájdeme najvyšší zapnutý bit a všetky nižšie bity v odpovedi zapneme.

Takto sme teda dosiahli zložitosť \(O(qn)\), čo je ale stále príliš pomalé. Ďalšia optimalizácia by mala ale byť každému skúsenému KSPákovi jasná – máme nejaké updatey a nejaké query na intervale (s asociatívnou kombinačnou funkciou) , takže na to proste hodíme intervaláč. Takto dosiahneme zložitosť \(O(n + q \log n)\), ktorá získa dva body.

Späť k pôvodnej úlohe

No a teraz sa ešte potrebujeme zbaviť obmedzenia \(a_i = 0\). Na to použijeme jedno veľmi pekné pozorovanie – pozrime sa na spoločný prefix čísel \(a_i\) a \(b_i\) v binárke. Vieme, že každé číslo v intervale \([a_i, b_i]\) má tiež tento prefix. Teda akúkoľvek hodnotu si vyberieme, tento prefix nedokážeme zmeniť. Nazvime si tieto bity fixnuté. No a tu nadchádza ďalšie pozorovanie – ingorujúc prípad \(a_i = b_i\), ktorý vieme triviálne vyriešiť, sa tieto čísla musia na prvej cifre po prefixe líšiť. To ale znamená, že v tomto intervale je aj toto \(b_i\), aj číslo, ktoré má na tejto líšiacej pozícií nulu a nižšie jednotky. Tiež ak je na niektorej nižšej pozícií jednotka, vieme ju vynulovať a nižšie dať jednotky.

No a tak sa nám rysuje riešenie: najprv si pre každé \(i\) spočítame najdlhší zhodný prefix \(a_i\) a \(b_i\). Následne si hodnoty \(b_i\) rozdelíme na tento prefix a zvyšok. Tieto dve časti si uložíme do intervaláča. Pri vykonávaní query si najprv vyORujeme tieto fixné prefixy. A následne už len pokračujeme v riešení prípadu \(a_i = 0\), akurát začíname s \(O\) nastaveným na OR fixných prefixov a pracujeme len na zvyškoch.

Ešte by sme si mohli myslieť, že sa nám v zložitosti opäť objaví \(\log A\) pri hľadaní najdlhšieho zhodného prefixu, avšak tomu sa vieme jednoducho vyhnúť tak, že \(a_i\) a \(b_i\) vyXORujeme a nájdeme najvyšší nastavený bit, čo moderné CPU zvládnu v konštantnom čase.

Toto riešenie má zložitosť \(O(n + q \log n)\) a získa plné body. Pamäťová zložitosť je \(O(n)\).