7. Nevítaný hosť s chlpatým kožuchom vzorové riešenie

3
1
1 1 5 1
1
1 1 1 5
1
1 1 3 3

5
5
5

1
3
4 1 4 1
2 2 3 2
1 2 1 4

6

...A  1s  ....  2s  ....  3s  ....  4s  ....  5s  ....  6s  ....
CBB.  -\  .PPn  -\  ..PP  -\  ...P  -\  ....  -\  ....  -\  ....
C...  -/  Pn..  -/  .Pn.  -/  ..Pn  -/  ...P  -/  ....  -/  ....
C...      P...      Pn..      .Pn.      ..Pn      ...P      ....

1
4
49 8 66 93
62 4 67 99
38 61 58 81
58 2 60 66

110

Zadanie úlohy je podobné Game of Life, ale s inými pravidlami. Pravidlá sú nasledovné:

1. Bunka \((x, y)\) je v novom kroku živá, ak aspoň dve z troch buniek \(\{(x, y), (x-1, y), (x, y-1)\}\) sú v aktuálnom kroku živé.
2. Inak je bunka v novom kroku mŕtva.

Plocha bude mŕtva v konečnom čase

Najprv si skúsme uvedomiť, že v každej situácii všetky bunky zomrú v konečnom čase. Všimnime si, že ak sa pozrieme na minimálne a maximálne súradnice všetkých buniek, tak žiadna bunka mimo obdĺžnika \((x_{min}, y_{min}, x_{max}, y_{max})\) nebude nikdy živá. Pre ľubovoľný vstup je teda konečne veľa buniek, ktoré môžu byť potenciálne živé. Pozrime sa na najhorší možný prípad, kedy na začiatku sú všetky bunky v tomto obdĺžniku živé (toto je naozaj najhorší prípad, keďže na rozdiel od Game of Life bunky nezomierajú, ak ich je niekde veľa). V každom čase, kedy existuje aspoň jedna živá bunka existuje aj niekoľko buniek, ktorá majú najmenšie \(y\) a v rámci nich existuje práve jedna bunka, ktorá má zároveň najmenšie \(x\) spomedzi nich. Táto bunka určite zomrie a už nikdy neožije. Keďže v každom kroku zomrie aspoň jedna bunka, žiadne bunky nepribúdajú a buniek je konečne veľa, všetky bunky zomrú v konečnom čase.

Simulácia – sada 1/5

Vyriešme prvú sadu priamočiarou simuláciou. Pamätajme si všetky bunky v 2D mriežke. V každom kroku sa pozrieme na každú bunku a podľa pravidiel zo zadania určíme, či bude živá alebo nie.

Toto by malo časovú zložitosť \(O([\text{veľkosť mriežky}] \cdot [\text{odpoveď}])\). Nech rozmer plochy je \(S\). Najhorší vstup čo môžeme dostať je mriežka \(S \times S\) plná živých buniek. Dá sa ukázať, že na tejto ploche všetky bunky zomrú za \(2 \cdot S - 1\) krokov. Teda časová zložitosť je \(O(S^3)\) a pamäťová \(O(S^2)\).

Tento kód môžeme trochu zoptimalizovať tak, že si nám stačí pamätať iba živé bunky (tých by malo byť zvyčajne oveľa menej ako tých mŕtvych) – na to môžeme použiť množinu (Python set, C++ std::unordered_set). V každom kroku sa potom nemusíme pozerať na každé políčko, ale iba na tie, ktoré sú blízko živých. Konkrétne nám stačí pre každú živú bunku skontrolovať, či zostane žiť a či vďaka nej neožije jej pravý sused. Avšak pre hore spomenutý najhorší vstup (\(S \times S\)) bude mať toto riešenie rovnakú časovú zložitosť.

Záleží na komponentoch

Dve bunky alebo obdĺžniky nazveme susedné, ak zdieľajú hranu alebo pravohorný-lavodolný \(\nearrow\swarrow\) roh. Teda nasledujúce konfigurácie buniek/obdĺžnikov nazývame susedné:

Fig. 1
     A. AB .A
     B. .. B.

Ďalej budeme hovoriť, že ak sú dve bunky/obdĺžniky susedné, tak patria do toho istého komponentu. Táto vlastnosť je tranzitívna, teda ak \(A-B\) patrí do toho istého komponentu a \(B-C\) patria do toho istého komponentu, tak aj \(A-C\) patria do toho istého komponentu.

Tvrdíme, že komponenty sú vždy súvislé a navzájom nezávislé. Ak si skúsime vytvoriť vstupy pre túto úlohu, môžeme si všimnúť, že ak na začiatku existovali nejaké komponenty, tieto komponenty sa počas celej simulácie nikdy neovplyvnili, nespojili ani nerozdelili na viac komponentov.

Ak je toto pravda, úlohu vieme riešiť samostatne pre každý komponent a výsledok bude maximum z výsledkov pre jednotlivé komponenty.

Dôkaz uvedieme neskôr.

Záleží na diagonálach

Podobne ak sa pozeráme na simuláciu jedného komponentu tak si všimneme, že bunky zomierajú a vznikajú v skupinách na diagonálach. Pozrite sa ako sa správa tento vstup:

Fig. 2
     OOOO   .OOO   ..OO   ...O   ....   ....   ....   ....
     O...   Oo..   .Oo.   ..Oo   ...O   ....   ....   ....
     O...   O...   Oo..   .Oo.   ..Oo   ...O   ....   ....
     O...   O...   O...   Oo..   .Oo.   ..Oo   ...O   ....

V každom kroku zomrie jedna diagonála a jedna nová ožije. Komplikovanejšie vstupy sa budú správať podobne.

Spomeňme si na argument, ktorý sme spravili na začiatku, že v každom kroku zomrie aspoň jedna bunka. Tento argument môžeme rozšíriť na celú diagonálu – v každom kroku zomrú všetky bunky na najľavohornejšej diagonále. Navyše, keďže išlo o najľavšiu diagonálu, tieto bunky už nikdy neožijú.

Odbočka – Simulácia s kladivom – sada 2/5

Pozrime sa na jeden komponent. Simulovať bunku po bunke je pomalé, ale už sme si všimli, že diagonály sú zaujímavé. Predstavme si, že na ploche sa nachádza jedna diagonála. Čo sa s ňou stane v ďalšom kroku? Táto jedna diagonála celá umrie, lebo žiadna bunka nemá naľavo a hore živé bunky. Ale vedľa tejto diagonály ožije nová diagonála, ktorá bude o jedno políčko kratšia.

Na diagonále naraz ožívajú, zostávajú žiť alebo umierajú veľké intervaly políčok. Vieme sa na tento proces pozrieť zametaním. Začneme v najľavejšej diagonále a zametáme smerom doprava dole. Implementovať krok vieme nasledovne:

• pre každý interval živých buniek sa tento interval v ďalšom kroku zmenší o jedna
• tým, že na ploche sú pôvodne nejaké obdĺžniky, medzi jednotlivými krokmi musíme manuálne pridať nejaké intervaly
• táto kolekcia intervalov a zmeny na nich sa dajú implementovať pomocou usporiadanej množiny alebo intervalového stromu.

Akú to bude mať časovú zložitosť? Časovú zložitosť budú dominovať operácie s intervalovým stromom. Jednak doňho pridávame nové diagonály a dvak v každom kroku zmenšujeme všetky intervaly. Nech počet buniek na začiatku je \(Z\). Ukážeme, že počet týchto operácií je \(O(Z)\), a teda časová zložitosť \(O(Z \log Z)\). Uvedomme si, že jediný spôsob akým pribúdajú políčka do intervalového stromu je tým, že pridávame diagonály. Pravidlá množenia sa plesne sme transformovali na pravidlo, že živý interval sa v ďalšom kroku presunie do susednej diagonály a skráti o jedna. Navyše jediný spôsob ako vie políčko zomrieť je tak, že zmizne skrátením intervalu o jedna. Počet týchto skrátení bude teda presne toľko, koľko políčok pridáme do intervalového stromu a to je nanajvýš \(Z\). Máme teda horný odhad. Zároveň je to presný odhad, keďže to vieme dosiahnuť napríklad vstupom:

Fig. 3
1 1 1 1000000
1 1 1000000 1

Pre obmedzenia druhej sady (obmedzenia na veľkosť súradníc a počet živých políčok) je najhorší vstup nasledovného tvaru (veľa vyššie spomenutých vstupov (Fig. 3) vložených do seba):

Fig. 4
     AAAAAAAA...A
     B
     B CCCCCC...C
     B D
     B D EEEE...E
     B D F
     B D F GG...G
     B D F H.
     . . . . .
     . . . .  .
     . . . .   .
     B D F H    .

Dá sa ukázať, že časová zložitosť je \(O(D \log D)\), kde \(D\) je počet živých diagonálnych intervalov na vstupe, avšak v tomto najhoršom prípade sú \(D\) a \(Z\) skoro rovnaké. Znamená to ale, že na vstupe s približne štvorcovými počiatočnými plochami (hore uvedený vstup má mimoriadne neštvorcové plochy) by mal tento algoritmus zložitosť \(O(\sqrt Z \log Z)\).

Zatiaľ sme však nespomenuli, ako hľadať komponenty.

Zjednodušenie úlohy

Simuláciou sa veľmi ďalej nedostaneme, treba si úlohu zjednodušiť. Znova sa pozrime na jeden komponent. Ukázali sme, že ako prvá zomrie bunka v najľavejšej diagonále. Otázkou teda zostáva, kedy zomrie posledná bunka. Ak si trochu nasimulujeme ako sa hra správa, vieme si všimnúť, že ako posledná zomrie bunka, ktorej súradnice \((x, y)\) sú maximum \(x\)-ových a \(y\)-ových súradníc všetkých buniek. Úloha sa nám teda zjednoduší na hľadanie najspodnejšej a najpravejšej bunky komponentu (dôkaz neskôr). A to je triviálne, ak vieme, že máme na ploche iba jeden komponent. Zostáva nám teda pre každú bunku určiť, do ktorého komponentu patrí. A tu sa reálne začína úloha.

Zadanie: Na vstupe máme \(N\) potenciálne prekrývajúcich sa obdĺžnikov. Ak sa dva obdĺžniky prekrývajú, dotýkajú hranou alebo pravohornými-ľavodolnými \(\nearrow\swarrow\) rohmi, tak hovoríme, že obdĺžniky sú susedné. Susedné obdĺžniky patria do rovnakého komponentu. Nájdi komponenty.

Určenie komponentov na úrovni buniek – sada 2/5

Toto riešenie dostane rovnako veľa bodov, ako vyššie spomínaná simulácia kladivom, avšak je oveľa jednoduchšie na nakódenie.

V druhej sade máme zaručené, že súčet plôch všetkých obdĺžnikov je malý. Môžeme teda každú bunku považovať za vrchol, vytvoriť hrany medzi susednými bunkami a nájsť komponenty v tomto grafe. Pre každú bunku vieme, že je k nej iba konštantne veľa susedných buniek (6 smerov, navyše pre každú bunku stačí zohľadniť iba polovicu z nich a zvyšok zohľadní susedná bunka). Tento graf bude mať teda \(O(Z)\) vrcholov a hrán.

Určenie komponentov na úrovni obdĺžnikov – sada 3/5

Teraz už ideme konečne opísať riešenie, ktoré nám dá viac bodov a je dokonca stále veľmi jednoduché na naprogramovanie.

Podobne ako v predchádzajúcom riešení, snažíme sa zostrojiť graf a nájsť v ňom komponenty. Snažíme sa postaviť graf, kde každý obdĺžnik je vrchol a hrana vedie medzi obdĺžnikmi, ktoré sú susedné.

V tejto sade však vieme, že počet obdĺžnikov je taký malý, že si vieme dovoliť \(O(N^2)\) riešenie. Môžeme sa teda pozrieť na každú dvojicu obdĺžnikov, určiť v \(O(1)\) čase, či sú susedné, postaviť graf a nájsť komponenty. Dostaneme graf s \(O(N)\) vrcholmi a v najhoršom prípade \(O(N^2)\) hranami.

Určiť či sú obdĺžniky susedné je priamočiare a pozostáva iba z porovnania súradníc oboch obdĺžnikov a kontroly, či sa pretínajú, dotýkajú hranami alebo správnymi rohmi.

Hľadanie komponentov v postavenom grafe

Na hľadanie komponentov v grafe vieme použiť rôzne metódy – ľubovoľné prehľadávanie (DFS, BFS) alebo Union-Find.

Časová zložitosť DFS a BFS je \(O(V+E)\) a časová zložitosť Union-Find je \(O(E \alpha^{-1}(E))\). Čo je ale zaujímavé je, že Union-Find je nielen rýchlejšie naprogramovať, ale reálne aj beží rýchlejšie. Pre účely popisu však povieme, že použitím prehľadávania dostávame lineárnu zložitosť vzhľadom na počet hrán.

Bez ohľadu na to, aký prístup zvolíme, nie je nutné si graf explicitne konštruovať. Ak máme funkciu, ktorá nám pre dva vrcholy povie, či je medzi nimi hrana (teda napríklad funkciu susednosti dvoch obdĺžnikov), graf vieme používať iba implicitne.

Neexistuje \(O(N^2 \alpha^{-1}(N))\)

A dokonca ani \(O(N \cdot \log N \cdot \alpha^{-1}(N))\).

Čo tým myslím? Keď si pozrieme Wikipédiu, tá hovorí, že časová zložitosť \(M\) operácií Union-Findu je \(O(M \alpha^{-1}(N))\). Avšak ja tvrdím, že ak zavoláme funkciu UF.find alebo UF.join \(N \log N\) krát, časová zložitosť bude iba \(O(N \log N)\), nie \(O(N \cdot \log N \cdot \alpha^{-1}(N))\). Väčšina týchto volaní sa dokázateľne vykoná v \(O(1)\) čase.

Spomeňme si na analýzu Union-Find algoritmu, kde funkcia UF.find robí path compression a UF.join joinuje buď podľa ranku alebo veľkosti komponentu.

Potom vieme, že najhlbší strom, ktorý vie vzniknúť, bude mať hĺbku \(O(\log N)\) (kvôli rank join). A z toho vidno, že pre každý vrchol sa funkcia UF.find rekurzívne zavolá tiež maximálne iba \(O(\log N)\) krát (kvôli path compression). Ak sme pre nejaký vrchol \(\log N\) krát rekurzívne zavolali UF.find (teda že tento vrchol nebol priamo pod koreňom), tak už určite bude navždy priamo pod koreňom a všetky ďalšie volania nebudú rekurzívne.

Počet rekurzívnych UF.find volaní vieme teda ohraničiť ako \(O(N \log N)\). Pre \(M\) operácií bude časová zložitosť \(O(\max(M, \min(M, N) \log N))\), čo pre \(M \in O(N \log N)\) znamená \(O(N \log N)\) a nie \(O(N \cdot \log N \cdot \alpha^{-1}(N))\).

Zložitosť pre tretiu sadu je teda bez ohľadu na to, či použijeme BFS, DFS alebo Union-Find \(O(N^2)\).

Ďalšie zjednodušenia

Aby sa nám v ďalších sadách pracovalo ľahšie, zjednodušíme si vstup.

V prvom rade si súradnice skomprimujeme. Teda si pozbierame všetky \(x\)-ové súradnice, utríedime ich a prečíslujeme na hodnoty \(0\) až počet rôznych \(x\)-ových súradníc. Počet rôznych \(x\)-ových súradníc bude nanajvýš \(2N\).

Avšak, ak by sme to spravili takto, pokazili by sme si riešenie. Totiž, ak sme mali napríklad obdĺžniky (10, 20, 13, 21) a (17, 20, 19, 21), po prečíslovaní by sa z nich stali (0, 0, 1, 1) a (2, 0, 3, 1). Zatiaľ čo originálne dva obdĺžniky nie sú susedné, prečíslované obdĺžniky už sú. Preto, ak chceme takto prečíslovávať, pre každú \(x_1\) súradnicu by sme mali do prečíslovacieho zoznamu pridať aj \(x_1-1\). Potom budú dané obdĺžniky vyzerať nasledovne – (1, 1, 2, 2) a (4, 1, 5, 2). Počet súradníc bude teda nanajvýš \(3N\).

V druhom rade prestaneme používať uzavreté intervaly na obdĺžniky. Nepopierateľne sa s tým ľahšie programuje. Ak by sme túto zmenu spravili už v riešení tretej sady, funkcia na susednosť by bola oveľa krajšia. Avšak v tomto prípade nám to pomôže aj pri kompresii. Ak prestaneme používať uzavreté intervaly, zmizne hore popísaný problém a znova budeme mať iba nanajvýš \(2N\) rôznych súradníc (čo nám prakticky zrýchli program o viac ako 33 %).

Rovnako upravíme aj \(y\)-ové súradnice.

Obdĺžnikov je veľa, ale neprekrývajú sa – sada 4/5

Čo nám pomáha, že sa obdĺžniky neprekrývajú? Čo je problém s predchádzajúcim riešením? Ak sa všetky obdĺžniky pretínajú, vznikne graf s \(O(N^2)\) hranami (a taký vstup vieme triviálne zostrojiť). Čo však v prípade, že sa obdĺžniky nepretínajú? Dá sa ukázať, že počet hrán je v tomto prípade \(O(N)\).

Dôkaz málo susedností

Pozrime sa na dva susedné neprekrývajúce sa obdĺžniky. Ako môžu vyzerať? Buď je hrana jedného podúsekom hrany toho druhého, alebo sa obe prekrývajú čiastočne, alebo sa dotýkajú rohom.

Fig. 5
   AAA      AAAAAAAAA   AAAAAA         AAAAAA      AAA
BBBBBBBBB      BBB         BBBBBB   BBBBBB      BBB

Vidíme, že pre B sa môže takmer každá z týchto situácií stať iba nanajvýš raz (napríklad nemôžu sa dva obdĺžniky dotýkať jeho pravého horného rohu). Jediné, čo sa môže stať viackrát je, že viacero obdĺžnikov má hranu ako podúsek jeho hrany. V tejto situácii sa na to však vieme pozrieť z opačnej strany a znova povedať, že pre tieto menšie obdĺžniky môže existovať iba jeden nadobdĺžnik. Každá susednosť nám “vyrieši” aspoň jednu hranu alebo roh a keďže tých je \(O(N)\), tak celkovo môže existovať iba \(O(N)\) susedností.

Zametanie

Ako efektívne hľadať tieto susednosti? Celkom určite zametaním. Vďaka vlastnosti, ktorú sme hore ukázali, by malo fungovať veľa rôznych prístupov – či už riešenie používajúce std::map alebo intervalový strom. Dôležité je, že si obdĺžniky pozametáme a budeme efektívne hľadať susednosti na okrajoch.

Najjednoduchšie je spraviť dve zametania, jedno vertikálne a jedno horizontálne. Zamerajme sa teraz na vertikálne zametanie. Potom sa v rámci tohto zametania stačí sústrediť iba na susednosti, ktoré sú spôsobené situáciami zobrazenými vyššie (Fig. 5).

Ak robíme zametanie, budeme mať nejakú štruktúru, v ktorej si budeme pre aktuálny riadok pamätať aktuálne aktívne obdĺžniky. Potom, keď ideme na ďalší riadok, budeme musieť pridať niektoré nové obdĺžniky a niektoré nové obdĺžniky musíme odobrať. Najprv vyhodnotíme všetky susednosti, potom odstránime všetky obdĺžniky, ktoré treba odstrániť, a nakoniec pridáme všetky, ktoré treba pridať. Čo je zaujímavé je, že keďže robíme dve zametania, netreba vyhodnocovať žiadne susednosti medzi obdĺžnikmi, ktoré práve pridávame. Tie sa vyhodnotia v kolmých zametaniach.

Ako nájsť všetky susednosti? Očakávame, že naša zvolená štruktúra podporuje vrátenie všetkých prvkov, ktoré sa pretínajú s požadovaným intervalom. Napríklad pre std::set, kde kľúč je pair<x_1, x_2> vieme tieto prvky nájsť pomocou funkcie lower_bound – ak zavoláme set.lower_bound({x_2, -1}), dostaneme prvok, najľavejší interval, ktorý je napravo od a určite nesusedí s intervalom \((x_1, x_2)\). Podobne set.lower_bound({x_1, -1}) - 2 nám dá najpravější interval, ktorý je naľavo a určite nesusedí s intervalom \((x_1, x_2)\) (zamyslite sa, prečo -2). Stačí nám zavolať jedno z týchto volaní a potom iterovať cez všetky vedľajšie intervaly, až kým neprestaneme susediť. Vyššie sme ukázali, že susedností je \(O(N)\), takže celkovo týchto iterácií spravíme \(O(N)\).

Musíme implementovať nasledujúce operácie:

1. pridať interval
2. odobrať interval
3. iterovať cez všetky intervaly, ktoré susedia s daným intervalom

Celkovo bude časová zložitosť \(O(N \log N)\), keďže triedime a používame nejakú stromovú štruktúru.

Obdĺžniky sa ale môžu prekrývať – sada 5/5

Pozrime sa, aké všelijaké problémy nám môžu vzniknúť, keď sa obdĺžniky prekrývajú:

Fig. 6
     1      AAA     CC D   F
     2   BBBabaBBB  CCoDoooFoooo
     3   BBBbabBBB   ooDoEoFoGoHH
     4      AAA  Y   ooooooFoGoo
     5      X              F G

Pridajme obdĺžnik do prázdneho lazy intervalového stromu. Keďže je to lazy strom, na pridanie stačí navštíviť iba \(O(\log N)\) vrcholov (až \(2 \log N\) bude obsahovať lazy informáciu a po ceste sme navštívili až \(2 \log N\) ďalších predkov). V predchádzajúcej sade, kde sa žiadne obdĺžniky neprekrývali, sme mali vlastne zaručené, že každý vrchol je pokrytý nanajvýš jedným obdĺžnikom. V tejto sade, žiaľ, už túto peknú vlastnosť nemáme. Pamätajme si teda v každom vrchole pole obdĺžnikov. Keď lenivo pridávame nový obdĺžnik do \(O(\log N)\) vrcholov, je možné, že v ňom už nejaký obdĺžnik je. V tomto prípade by sme radi tiež dali tieto dva obdĺžniky do jedného komponentu.

Spravíme v tomto lazy intervalovom strome jednu zvláštnu vec, a to že si lazy informácie nebudeme propagovať ďalej. Ak štandardne máme vo vrchole zapamätanú premennú hodnota a lazy, tak v našom intervalovom strome nám stačí lazy (ktorá je pole identifikátorov obdĺžnikov). Prečo to robíme? Keďže chceme podporovať aj odoberanie obdĺžnikov, ľahšie sa nám to bude robiť, ak sa obdĺžniky nerozlezú až hlboko do listov. Ak by sme informácie propagovali, explicitné upratanie obdĺžnikov by potenciálne trvalo až \(O(N)\). Trochu sa nám týmto komplikuje vyhodnocovanie pretnutí pri pridávaní obdĺžnikov, ale to zvládneme vyriešiť.

Nazvime množinu vrcholov, ktoré pokrývajú interval prislúchajúci pridávanému obdĺžniku \(J\) (teda práve tie vrcholy, do ktorých by sme uložili lazy informáciu). Čo by sa zmenilo, keby sme každý obdĺžnik rozdelili na množinu nových obdĺžnikov tak, že každý pokrýva práve jeden vrchol z \(J\). Celý algoritmus by mal naďalej fungovať (keďže takýto vstup existuje), iba sa nám zložitosti zhoršia o logaritmus, pretože máme o logaritmus krát viac obdĺžnikov. Robiť to teda nebudeme, ale bez ujmy na všeobecnosti nad tým tak môžeme uvažovať.

Pozrime sa teda iba na jeden vrchol z \(J\). Pridaný obdĺžnik prejde v intervalovom strome nejakú cestu. Naším cieľom je ho spojiť so všetkými ostatnými obdĺžnikmi, ktoré sa s ním pretínajú. Teda nájsť všetky obdĺžniky, ktorých cesta je buď podmnožina (starý obdĺžnik pokrýva celý nový obdĺžnik) alebo nadmnožina (nový obdĺžnik pokrýva celý starý obdĺžnik). Každú dvojicu ciest stačí spracovať iba raz. Rozumné miesto kde to robiť je v koncovom vrchole kratšej cesty.

Fig. 7                 1       2       3       4       5
     1   AAAAAAAA      A       A       A       A       .
     2   AAAABBAA     / \     / \     / \     / \     / \
     3   AAAABBCC    .   .   .   .   .   C   .   C   .   C
     4   AAAACCCC       / \     / \     / \     / \     / \
     5       CCCC      .   .   B   .   B   .   .   .   .   .

Na obrázku (Fig. 7) vidíme, ako by vyzeral intervalový strom v jednotlivých časových bodoch zametania. Vidíme, že cesta do vrcholu s obdĺžnikom \(B\) je nadmnožina cesty do vrcholu pre \(A\) (rovnako aj pre dvojice \(C-A\) a \(B-C\)). O spojenie \(A-B\) a \(A-C\) sa teda chceme postarať v \(A\) a o spojenie \(B-C\) v \(C\).

Pozrime sa čo sa deje v tomto koncovom vrchole \(V\) pre nový obdĺžnik. Chceme pridať obdĺžnik do \(V\) a celý ho pokryť. Pod \(V\) môže byť viacero doposiaľ disjunktných obdĺžnikov a týmto ich všetky dostaneme do jedného komponentu:

Fig. 8
            A  B
            A  B
     XX...XXaXXbXXXX...XX
            A  B
            A  B
     WW...WWaWWbWWgW...WW
            A  B  G
            A  B
     YY...YYaY B  H
            A  B
            A  B
            A ZbZZZZ...ZZ
            A  B

Povedzme, že v tomto prípade (Fig. 8) zametáme zhora nadol, \(X\) pokrýva nejaký veľký interval a tým, že ho pridáme, spojíme obdĺžniky \(A\), \(B\) a \(X\) do jedného komponentu. Keďže \(A\) a \(B\) sú veľmi úzke, v intervalovom strome je \(J_A\) a \(J_B\) iba jeden list. Ak by sme pri pridávaní \(X\) do intervalového stromu išli až po úroveň listov, vykonali by sme až \(O(N)\) operácií pre jeden obdĺžnik. Namiesto toho, aby sme teda chodili do všetkých potomkov \(J\), pamätajme si informáciu o prítomnosti obdĺžnika aj vo všetkých predkoch \(J\). Tých je iba nanajvýš \(O(\log N)\). Informáciu o prítomnosti obdĺžniku si teda pamätáme na celej spomínanej ceste a zjednotenie všetkých ciest pre \(J\) má veľkosť iba \(O(\log N)\).

Ak by sme sa však pokúsili spojiť nový obdĺžnik so všetkými obdĺžnikmi vo \(V\), mali by sme stále zlú časovú zložitosť. Obdĺžniky sa nám vo vrcholoch hromadia a každý môže obsahovať až \(O(N)\) obdĺžnikov (avšak všetky vrcholy dokopy majú stále iba \(O(N \log N)\)). Preto je dôležité, že nový obdĺžnik pokrýva celé intervaly prislúchajúce vrcholom z \(J\). Vieme si teda predstaviť, že aj keď máme vo vrchole \(V\) zapamätaných povedzme tisíc obdĺžnikov, pridaním tohoto nového obdĺžnika sa všetkých tisíc spojí do jedného komponentu. Pri pridávaní ďalšieho obdĺžnika by ho stačilo spojiť s týmto veľkým komponentom, namiesto spájania s tisíc obdĺžnikmi. Nový obdĺžnik vyrieši/vyčistí všetky vrcholy z \(J\), tak že v nich zostane iba jeden komponent. Tento prístup je teda ako keby sme si v každom vrchole pamätali nezávislú Union-Find štruktúru.

Problémy nastanú, keď sa pokúsime obdĺžnik odstrániť – ako na obrázku (Fig. 8). Ak odstránime obdĺžnik \(X\), nastanú dva problémy. Jednak sme potenciálne odstránili koreň nejakého Union-Find komponentu. Dvak, keďže \(X\) pokrýval celý interval od \(A\) po \(B\), ako zaručíme, že nebudeme znova vykonávať veľa práce pri pridávaní obdĺžnika \(W\)?

Prvý problém nie je problém, za koreň zvolíme ľubovoľného potomka. Pre druhý problém je dôležité to, že obdĺžnik \(W\) pokrýva celý interval daného vrcholu. Keďže odstránením vrcholu sa komponenty Union-Findu nerozpadli a \(W\) pokrýva celý interval, stačí \(W\) spojiť iba so všetkými koreňmi Union-Find komponentov, čím znova vyčistíme daný vrchol a amortizovane spotrebujeme \(O(1)\) času.

Týmto by sme mali celkom vyriešené spájanie s nadmnožinovými cestami. Čo tie podmnožinové? Teda ako sa zachovať keď pridávame obdĺžniky \(G\) a \(H\)? Stále ich chceme vyriešiť v koncovom vrchole tej kratšej cesty. To znamená, že po ceste dole intervaláčom sa pozeráme, či aktuálny vrchol nie je koncovým pre nejaký obdĺžnik. Môže byť dokonca koncovým pre viacero, ale znova si uvedomme, že v tom prípade budú určite všetky patriť do toho istého komponentu. A ak taký existuje, tak to musí znamenať, že všetky obdĺžniky v tomto vrchole patria do jedného komponentu. Pozor, ide o implikáciu, nie ekvivalenciu – to, že existuje iba jeden komponent neznamená, že existuje obdĺžnik čo pokrýva celý interval. Zamyslite sa, ako zistiť, či existuje pokrývajúci obdĺžnik. V tom prípade nový obdĺžnik tiež pridáme do tohoto veľkého komponentu, inak vytvoríme nový komponent obsahujúci iba nový obdĺžnik.

Všimnime si, že nám nevadí vytvárať veľa malých komponentov. Je možné, že vo vrchole pre interval dĺžky 16 budeme mať tisíc jednoprvkových komponentov. Očividne by sa počet komponentov dal zredukovať na nanajvýš 16. My však chceme byť efektívny, a teda lenivý. Túto redukciu si odložíme na moment, keď pridáme obdĺžnik, ktorý bude mať tento vrchol vo svojom \(J\). Tým, že by sme to spravili skôr si nič nepomôžeme, keďže všetky dôležité spojenia komponentov sa vyriešili na hlbších vrstvách intervalového stromu.

Teraz si môžeme všimnúť, že vo vrchole si vždy pamätáme jeden veľký komponent a kopu jednoprvkových komponentov, ktoré sa doňho dostali z jeho potomkov. Môžeme tomu teda prispôsobiť implementáciu a nemusíme si vo vrchole pamätať Union-Find, ale iba nejaké dve množiny (napríklad std::unordered_set) – jednu pre veľký komponent a druhú pre jednoprvkové komponenty. Množinu používame, aby sme vedeli rýchlo odstraňovať prvky.

std::unordered_set má síce \(O(1)\) operácie, nie je však taký rýchly ako pole. Implementáciu vieme teda vylepšiť tým, že si budeme pamätať dve polia a hodnoty z nich nemažme. Hodnoty v poliach totiž používame iba ak ich chceme všetky spojiť do jedného komponentu, teda zobrať všetky hodnoty z druhého pola a nasypať ich do prvého. Keď už toto robíme, vieme si pre každý prvok skontrolovať, či je ešte živý (rects[ri].y2 >= sweep_time) a ak nie, jednoducho ho odignorovať. Dajme si pozor, aby sme nehýbali s prvkami vo veľkom komponente (to by nám pokazilo časovú zložitosť). Na to, či vo veľkom komponente existuje ešte aspoň jeden aktívny obdĺžnik si budeme pamätať maximálnu koncovú súradnicu zo všetkých obdĺžnikov v ňom (podobne riešime zamyslenie nad existencie pokrývajúceho obdĺžnika). Celé toto nás bude stáť zopár riadkov, ale kód by mal byť oveľa rýchlejší.

Týmto sme vyriešili pridávanie a odoberanie obdĺžnikov a spájanie tam, kde sa prekrývajú. Spájanie tam kde sa dotýkajú doriešime všeliako na kolene, keďže stačí skontrolovať iba \(O(\log N)\) vrcholov, ktorých intervaly sa dotýkajú pridávaného obdĺžnika.

Premeníme intervaly vstupe na polootvorené a skomprimujeme si súradnice. Zametáme, pričom si pamätáme globálnu Union-Find štruktúru. Máme lazy intervalový strom v ktorom nepropagujeme a vo vrcholoch si pamätáme dve polia a pomocné agregačné informácie o tom prvom. Obe polia obsahujú indexy nejakých obdĺžnikov, pričom v prvom poli sú všetky súčasťou jedného komponentu a v druhom sú všekty zatiaľ ako samostatný komponent. Agregačné informácie pre prvé pole sú: o aký komponent ide, dokedy je ešte niečo aktívne a dokedy je ešte nejaký plne pokrývajúci prvok aktívny. Keď pridávame obdĺžnik, po ceste kontrolujeme, či je vrchol pokrytý jedným obdĺžnikom a podľa toho pridáme nový obdĺžnik do prvého alebo druhého pola. Keď prídeme do vrcholu, ktorý nový obdĺžnik celý pokrýva, skončíme rekurziu. Presypeme druhé pole do prvého, pričom ignorujeme neaktívne prvky. Aktualizujeme agregačné informácie. Vždy keď dávame prvok do prvého pola, spojíme ho v globálnom Union-Finde s daným komponentom. Počas rekurzie vyriešime aj dotýkajúce sa obdĺžniky. Obdĺžniky pri zametaní teda explicitne nemažeme. Skončime s Union-Find štruktúrou, ktorá určuje rozdelenie obdĺžnikov do nezávislých komponentov.

No a toto je prakticky celé riešenie. Časová a pamäťová zložitosť sú \(O(N \log N)\).

Dá sa to aj lepšie

Predsa len, komu sa chce pamätať si pole alebo nebodaj std::unordered_set vo vrcholoch intervalového stromu. Keď namiesto toho sa môžeme ďalej zamyslieť nad tým, čo sa ako deje a v každom vrchole si pamätať iba \(O(1)\) informácie.

Znova majme lazy intervalový strom, ale tentokrát budeme informácie aj propagovať. To preto, lebo z neho nebudeme explicitne mazať veci. Pre každý vrchol si budeme snažiť zapamätať, aký najdlhšie žijúci komponent v ňom je, do akého času bude žiť a ktorý obdĺžnik ho reprezentuje — (life, kompid, rectid). life je v tomto prípade najväčšia koncová súradnica spomedzi všetkých obdĺžnikov na danom intervale (ľubovoľný čo doň zasahuje). Ak máme takúto informáciu pre dva intervaly, tak informácia pre ich zjednotenie je jednoducho ich maximum. Keď pridávame nový obdĺžnik, túto informáciu si vypýtame pre celý jeho interval. Vďaka nej potom vieme povedať, či sa obdĺžnik s niečím pretne alebo nie (ak life >= y_1, tak áno, inak nie).

Zistili sme, že sa pretneme s nejakým obĺžnikom \(R\). Predpokladáme, že on už je pospájaný do jedného komponentu so všetkými ostanými obdĺžnikmi, ktoré sú celé v ňom. Interval nového obdĺžnika teda môžeme rozdeliť na dva nezávislé kratšie úseky naľavo a napravo od \(R\) a rekurzívne sa pýtať intervalového stromu. Tu je problém, že odpovede naľavo a napravo vedia patriť do toho istého komponentu ako \(R\) a pokazíme si časovú zložitosť.

Pre každý komponent si pamätajme intervaly, ktoré pokrýva. Potom nebudeme deliť interval nového obdĺžnika na dva menšie podúseky, ale na veľa podúsekov, ktoré sú pomedzi intervaly komponentu \(komp[R]\). Na tieto podintervaly sa stále vieme zavolať rekurzívne. Samozrejme, týchto podintervalov môže byť veľa a môžu byť aj prázdne. To sa môže zdať ako strata času. Dôležité je, že pridaním tohto nového obdĺžnika tieto intervaly zaplníme a odstránime zo zoznamu intervalov pre \(komp[R]\). Ak bol interval prázdny alebo sa nič nepretlo, tak nový obdĺžnik bude určite žiť na tomto intervale v intervalovom strome dlhšie ako čokoľvek čo tam bolo doteraz. Ak sa obdĺžnik pretne, počet komponentov klesne o jedna. Amortizovane bude táto operácia trvať rovnako dlho, koľko existuje intervalov a komponentov. Teraz si už iba stačí uvedomiť, že pridaním nového obdĺžnika vieme vytvoriť iba konštantne veľa nových intervalov. Na to, aby sme vytvárali, pridávali a odoberali nové intervaly, si budeme pre každý komponent pamätať std::set a robiť tieto operácie efektívne na ňom. Intervalov a komponentov bude nanajvýš \(O(N)\), a teda časová aj pamäťová zložitosť budú \(O(N \log N)\).

Zamyslite sa, ako bude tento algoritmus prebiehať na takomto vstupe pri zametaní zhora nadol:

Fig. 8
     AAAAAAAAAAA
     B         C
     B  DDDDD  C
     B  DDDDD  C
     B         C

Aj ak sa nepretneme, musíme sa rekurzívne zavolať na podintervaly, aby sme správne modifikovali zoznamy intervalov pre komponenty.

Naozaj prosím žiadne sety

Ale komu sa chce spájať a rozpájať nejaké intervaly v sete. Vystačíme si iba s intervalovým stromom. Problém bol, že prvým zavolaním sme efektívne našli pretínajúci komponent, avšak ďalšie volania nám mohli dávať ten istý komponent. Napríklad ak by hodnoty life v intervalovom strome boli 1 2 3 4 5 4 3 2 1 a všetky patrili do toho istého komponentu, tak by sme vykonali \(O(N)\) volaní.

My sme však ukázali, že intervalov, ktoré patria do rôznych komponentov, je celkovo iba \(O(N)\). Rovnakú myšlienku sme použili na riešenie štvrtej sady! Tam sme ukázali, že existuje nanajvýš \(O(N)\) disjunktných intervalov rôznych obdĺžnikov. Tu sme ukázali, že existuje nanajvýš \(O(N)\) disjunktných intervalov rôznych komponentov. Na dosiahnutie dobrej časovej zložitosti nám stačí dané riešenie prispôsobiť na komponenty, teda efektívne implementovať 3. operáciu — iterovanie.

Pre ľubovoľný list intervalového stromu chceme efektívne (\(O(\log N)\)) nájsť najbližší list napravo od neho, ktorý patrí do iného komponentu (alebo žiadneho). So správnymi údajmi môžeme výsledok “binárne vyhľadávať”. Vo vrcholoch si budeme pamätať dodatočné informácie:

1. či je celý interval pokrytý jedným komponentom alebo nie
2. do akého komponentu patrí najľavejší list tohto intervalu
3. do akého komponentu patrí najpravý list tohto intervalu

Ak máme túto informáciu pre dva susedné intervaly, vieme ju jednoducho zistiť aj pre ich zjednotenie (zmena je buď v ľavom, pravom alebo na hranici intervalu).

Treba sa zamyslieť, ako tieto informácie ovplyvnia lazy updaty. Lazy update robíme iba ak pokrývame celý interval. V tom prípade v danom intervale určite nebude žiadna zmena komponentu a ľavý aj pravý okraj budú mať hodnotu nového komponentu.

Ako teda binárne vyhľadávať? Sme v nejakom liste a chceme nájsť najbližšiu zmenu komponentu napravo od nás. Budeme bublať smerom dohora. Ak sme pravé dieťa, tak s tým nič nenarobíme. Ak sme ľavé dieťa, tak najbližšia zmena je potenciálne v našom súrodencovi alebo na hranici medzi nami. To vieme okamžite zistiť tak, že sa pozrieme na predpočítanú informáciu. Inak pokračujeme v bublaní dohora. Ak je nejaká zmena v našom súrodencovi, tak bubleme dodola. Ak je zmena v jeho ľavom synovi, tak ideme tam, inak je možno na rozmedzí a inak musí byť v pravom synovi. Potrvá nám \(O(\log N)\) času vybublať hore a dole a nájsť najbližší odlišný komponent. Počas tohoto si treba dať pozor na správne propagovanie lazy informácii.

Zmenili sme intervali na polootvorené, skomprimovali sme si súradnice, vytvorili Union-Find štruktúru a lazy intervalový strom, zametáme jedným smerom. Pridanie jedného obdĺžnika potrvá \(O(\log N)\) (Union-Find operácie sa amortizujú na \(O(1)\)). Obdĺžniky neodoberáme, iba ich začneme ignorovať, ak sú príliš staré (ich koncová súradnica je malá). Nájdenie najbližšieho susedného obdĺžnika trvá \(O(\log N)\) a zavoláme to \(O(N)\) krát. Celková časová zložitosť je \(O(N \log N)\), pamäťová \(O(N)\) a set sme použili iba pri kompresií súradníc.

Dôkazy

Diagonála je určená ako všetky bunky, ktorých \(x + y = C\).

Komponent s jednou živou bunkou je triviálny prípad, takže predpokladáme, že každý komponent má aspoň dve živé bunky.

Lema 1: Ak máme jeden komponent a diagonála \(x+y=C\) je najmenšia diagonála, ktorá obsahuje živé bunky, potom v ďalšom kroku žiadna bunka nebude na diagonále \(C\) a nejaká bunka bude na diagonále \(C+1\).

Dôkaz: Pozrime sa na bunku s najväčším \(y\) na diagonále \(C\). Keďže ide o jeden komponent s aspoň dvoma bunkami, musí existovať aspoň jedna bunka na pozíciách \(\leftarrow\rightarrow\uparrow\downarrow\nearrow\swarrow\). Pozície \(\uparrow\leftarrow\swarrow\) sú v rozpore s tým, že ide o bunku s najväčším \(y\) na diagonále \(C\). Pozície \(\downarrow\rightarrow\) sú bunky na diagonále \(C+1\), ktoré vďaka tejto bunke tento krok prežijú, čo spĺňa Lemu. Nakoniec pozícia \(\nearrow\) znamená, že ak na pozícii \(\rightarrow\) nie je živá bunka, v ďalšom kroku tam ožije, čo spĺňa Lemu. ∎

Lema 2: Súvislý komponent v ďalšom kroku zostane súvislý.

Dôkaz: Sporom. Predpokladajme, že sa komponent rozdelil.

Jedna možnosť je, že sa vytvoril nový komponent alebo komponenty, ktoré nie sú napojené navzájom alebo k pôvodnému. Na začiatok si uvedomme, že nemôžu vzniknúť dva rôzne komponenty a zároveň všetky bunky z predchádzajúceho komponentu zaniknúť. Stačí sa teraz sústrediť na to, či môže vzniknúť nový komponent, ktorý nie je napojený na na nejakú preživšiu bunku.

Prepokldajme, že sa také stalo. Tento komponent bude mať tvar iba jednej diagonály. Bez ujmy na všebecnosť zoberme najmenšiu možnú diagonálu, teda jednu bunku (obdobný dôkaz sa aplikuje na ľubovoľne dlhú diagonálu).

Keďže vznikla nová bunka, ktorá nie je na nič napojená, obe bunky \(\leftarrow\uparrow\) čo ju stvorili musia zomrieť a v jej okolí \(\leftarrow\rightarrow\uparrow\downarrow\nearrow\swarrow\) nesmú zostať žiť žiadne:

       -   >     A   =     A
      -†   >    †-   =    †a
     -†    >   †x-   =   †x-
           >  B--    =  Bb-

Kde † reprezentujú \(\leftarrow\uparrow\) bunky, na - nesmie byť živá bunka a na A alebo B musí byť aspoň jedna živá bunka (inak je toto celý komponent a Lema platí). To ale spôsobí, že na a alebo b vznikne bunka, čím dostávame spor s tým, že vznikla diagonála dĺžky iba jedna.

Alternatívne sa komponent rozdelí tým, že niektorá bunka zomrie.

      -A
     -†B
     DC

V tomto prípade † je bunka čo v ďalšom kroku zomrie, na - nesmie byť bunka a na ABCD musí byť aspoň jedna živá bunka. Ak by na ABCD bola práve jedna alebo všetky štyri živé bunky, † nespôsobí rozdelenie komponentu. Ak na ABCD budú tri živé bunky, tak je to iba jednoduchšia situácia ako dve živé bunky. Ak na ABCD budú práve dve živé bunky, máme 6 možností. Vieme si overiť, že pre žiadnu z nich sa komponent lokálne nerozpadne, pretože buď zostanú niektoré ABCD bunky žiť alebo vďaka † vzniknú nové. Prípady kedy AB, BC alebo CD žijú sú triviálne. Názorne si ukážeme prípad kedy AD sú živé a ostatné prípady by sa dali ukázať obdobne. V ďalšom kroku určite budú bunky BC žiť a niektoré z AD možno zomrú. Ak niektorá z buniek AD prežije, na danej strane komponentu ide o nezaujímavý prípad, keďže komponent sa tam nerozpadne. Ak však povedzme A zomrie, argument vieme posunúť o jedna ďalej, prepísať †->D, A->† a pozrieť sa rovnako na túto situáciu. Takto to vieme posúvať ďalej a ďalej. Avšak buniek je konečne veľa, takže musíme prísť do prípadu, ktorý je triviálny a spĺňa Lemu. Následne spätne ukážeme, že aj všetky poposúvané situácie teda spĺňali Lemu.

Nie je to úplne najelegantnejší, ale hádam to je valídny dôkaz… ∎

Lema 3: Dva rôzne komponenty sa nikdy nespoja.

Dôkaz: Keďže komponenty sú rôzne, musí vzniknúť nejaká nová bunka, ktorá ich spojí. Na to, aby vznikla bunka, musia existovať bunky \(\leftarrow\uparrow\). Keďže tieto dve bunky sú susedné v \(\nearrow\swarrow\) smere, musia byť z toho istého komponentu (inak spor). Nová bunka musí susediť s druhým komponentom. Ak by susedila v jednom z \(\nearrow\swarrow\) smerov, tak máme spor, že komponenty sú rôzne (susedia s \(\leftarrow\uparrow\) bunkami). Ak je druhý komponent v smeroch \(\rightarrow\downarrow\), tak nám to nepomôže, keďže v čase, keď bunka vznikne, tieto bunky zomrú. Dva rôzne komponenty sa teda nikdy nemôžu spojiť. Preto sa rôzne komponenty ani nikdy neovplyvnia. ∎

Lema 4: V súvislom komponente sa maximálna súradnica \(X\) a \(Y\) živých buniek v ďalšom kroku nezmení.

Dôkaz: Ukážeme dôkaz pre maximálne \(Y\) a dôkaz pre maximálne \(X\) je obdobný. Pozrime sa na bunku s maximálnym \(Y\). Keďže ide o súvislý komponent s aspoň dvoma bunkami, existuje aspoň jedna živá bunka v smeroch \(\leftarrow\rightarrow\uparrow\downarrow\nearrow\swarrow\). Smery \(\downarrow\swarrow\) sú v rozpore s tým, že táto bunka má maximálne \(Y\). Smery \(\leftarrow\uparrow\) spôsobia, že táto bunka v ďalšom kroku prežije, čo spĺňa Lemu. Smery \(\rightarrow\nearrow\) spôsobia, že bunka \(\rightarrow\) v ďalšom kroku bude žiť, čo spĺňa Lemu. ∎

Spojením Lemy 1 a 4 sme ukázali, že dĺžka prežitia komponentu je \(X+Y-C\), kde \(X\) je maximálna \(x\) súradnica komponentu, \(Y\) maximálna \(y\) súradnica komponentu a \(C\) je najmenšia diagonála, teda najmenšie \(x+y\) spomedzi všetkých buniek komponentu.

#include <bits/stdc++.h>
using namespace std;

struct UF {
    vector<int> e;
    UF(int n): e(n, -1) {}
    int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
    bool join(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return false;
        if (e[a] > e[b]) swap(a, b);
        e[a] += e[b];
        e[b] = a;
        return true;
    }
};

struct STval {
    // x coordinate, color, contains color change
    int maxi, c, firstc, lastc;
    bool ch;

    constexpr STval(): maxi(-1), c(-1), firstc(-1), lastc(-1), ch(false) {}
    STval(int maxi, int c, int firstc, int lastc, bool ch):
        maxi(maxi), c(c), firstc(firstc), lastc(lastc), ch(ch) {}
    bool isempty() const { return c == -1; }
    
    static STval merge(const STval &a, const STval &b) {
        bool ch = a.ch | b.ch | (a.lastc != b.firstc);
        return a.maxi > b.maxi ?
            STval(a.maxi, a.c, a.firstc, b.lastc, ch) :
            STval(b.maxi, b.c, a.firstc, b.lastc, ch);
    }
    void update(const STval &b) {
        if (b.maxi > maxi) {
            maxi = b.maxi;
            c = b.c;
        }
        ch = false;
        firstc = b.firstc;
        lastc = b.lastc;
    }
};

// lazy ST with range set
struct ST {
    using T = STval;
    static constexpr T unit = STval();

    int n;
    vector<T> val, lazy;
    vector<pair<int, int>> bound;

    ST(int _n) {
        for (n = 1; n < _n; n *= 2);
        val.resize(2 * n, unit);
        lazy.resize(2 * n);
        bound.resize(2 * n);
        for (int i = 0; i < n; ++i)
            bound[n + i] = {i, i+1};
        for (int i = n - 1; i > 0; --i)
            bound[i] = {bound[2 * i].first, bound[2 * i + 1].second};
    }

    void push(int i) {
        if (lazy[i].isempty()) return;
        val[i].update(lazy[i]);
        if (i < n) {
            lazy[2 * i].update(lazy[i]);
            lazy[2 * i + 1].update(lazy[i]);
        }
        lazy[i] = unit;
    }

    void update(int cur, int qlo, int qhi, T v) {
        if (qhi <= bound[cur].first || bound[cur].second <= qlo) return;
        if (qlo <= bound[cur].first && bound[cur].second <= qhi) {
            lazy[cur].update(v);
            return;
        }
        push(cur);
        for (int i: {0, 1}) update(2 * cur + i, qlo, qhi, v), push(2 * cur + i);
        val[cur] = STval::merge(val[2 * cur], val[2 * cur + 1]);
    }

    T query(int cur, int qlo, int qhi) {
        push(cur);
        if (qhi <= bound[cur].first || bound[cur].second <= qlo) return unit;
        if (qlo <= bound[cur].first && bound[cur].second <= qhi) return val[cur];
        return STval::merge(query(2 * cur, qlo, qhi), query(2 * cur + 1, qlo, qhi));
    }

    // find leftmost index ind in from qlo for which val[ind-1] != val[ind]
    int find_next_change(int qlo) {
        if (qlo >= n) return n + 1;
        {
            int path[30], len = 0;
            for (int cur = n + qlo; cur > 0; cur /= 2)
                path[len++] = cur;
            for (int i = len - 1; i >= 0; --i)
                push(path[i]);
        }
        int res = n + 1;
        for (int cur = n + qlo; cur > 0; cur /= 2) {
            if (!val[cur].ch) continue;
            assert(cur < n);
            push(cur * 2); push(cur * 2 + 1);
            if (val[cur * 2].lastc != val[cur * 2 + 1].firstc) {
                int r = bound[cur * 2 + 1].first;
                if (r > qlo) res = min(res, r);
            }
        }
        int cur = n + qlo;
        for (; cur > 0; cur /= 2) {
            if (cur % 2 || !val[cur + 1].ch) // we are right child or there is no change
                continue;
            cur += 1;
            break;
        }
        if (cur == 0) return n + 1;
        assert(cur < n);
        assert(val[cur].ch);
        while (cur < n) {
            push(cur * 2); push(cur * 2 + 1);
            if (val[cur * 2].ch) cur = cur * 2;
            else if (val[cur * 2].lastc != val[cur * 2 + 1].firstc) {
                cur = bound[cur * 2 + 1].first;
                break;
            } else if (val[cur * 2 + 1].ch) cur = cur * 2 + 1;
            else assert(false); // st is mangled up
        }
        assert(cur < n); // we should not end up in leaf
        res = min(res, cur);
        return res;
    }
};

struct Rect {
    int x1, y1, x2, y2, i;
};

UF find_components(vector<Rect> Rs) {
    set<int> xs, ys;
    for (auto &r: Rs)
        xs.insert(r.x1), xs.insert(r.x2), ys.insert(r.y1), ys.insert(r.y2);

    unordered_map<int, int> xmap, ymap;
    {
        int i = 0;
        for (auto x: xs) xmap[x] = i++;
        i = 0;
        for (auto y: ys) ymap[y] = i++;
    }

    for (auto &r: Rs) {
        r.x1 = xmap[r.x1];
        r.x2 = xmap[r.x2];
        r.y1 = ymap[r.y1];
        r.y2 = ymap[r.y2];
    }

    sort(Rs.begin(), Rs.end(), [](const Rect &a, const Rect &b) {
        return a.x1 < b.x1;
    });

    ST st(ymap.size());
    UF uf(Rs.size());
    for (auto &r: Rs) {
        { // topleft corner is special
            auto qres = st.query(1, r.y1-1, r.y1);
            if (qres.maxi > r.x1) uf.join(r.i, qres.c);
        }
        int qlo = r.y1, qhi = qlo + 1, maxq = r.y2;
        while (qlo <= maxq) {
            auto qres = st.query(1, qlo, min(qhi, maxq + 1));
            if (qres.maxi >= r.x1) uf.join(r.i, qres.c);
            qlo = qhi;
            qhi = st.find_next_change(qlo);
        }
        int col = uf.find(r.i);
        st.update(1, r.y1, r.y2, {r.x2, col, col, col, false});
    }

    return uf;
}

void solve() {
    int Rn;
    cin >> Rn;

    vector<Rect> Rs(Rn);
    for (int i = 0; i < Rn; i++)
        Rs[i].i = i;
    for (auto &r: Rs) {
        cin >> r.x1 >> r.y1 >> r.x2 >> r.y2;
        --r.x1, --r.y1;
    }

    auto uf = find_components(Rs);

    vector<int> minxy(Rn, 2.1e9), maxx(Rn, -1), maxy(Rn, -1);
    for (int i = 0; i < Rn; i++) {
        int c = uf.find(i);
        minxy[c] = min(minxy[c], Rs[i].x1 + Rs[i].y1);
        maxx[c] = max(maxx[c], Rs[i].x2 - 1);
        maxy[c] = max(maxy[c], Rs[i].y2 - 1);
    }

    int res = 0;
    for (int i = 0; i < Rn; i++)
        res = max(res, 1 + maxx[i] + maxy[i] - minxy[i]);

    cout << res << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int TC;
    cin >> TC;
    while (TC--) solve();
};