Zadanie
V T2 je špinavo. Dávid tam síce z času na čas povysáva, no Marcelovi to nestačí. Ako správny zdravotník si je vedomý toho, že pre odstránenie mikróbov bude nutné použiť niečo silnejšie. Doniesol si teda svoj tepovač a všetky koberce za doobedie dôkladne vyčistil.
Vtom si ale spomenul na ďalšiu nepríjemnosť. Totiž, vo vlhkom prostredí sa dobre darí plesniam. Zobral teda koberce a dal ich sušiť na slnečný trávnik. Trávnik je však malý a koberce sa nezmestia vedľa seba. Niektoré teda naukladal jeden na druhý. Nechcel ale, aby to bolo až príliš chaotické, nuž sa žiadne dva koberce nedotýkajú stranami ani rohmi. Môže však byť menší koberec položený na väčšom, alebo naopak.
Na slnečnom trávniku sa zvyknú hrávať deti. Nejaké koberce im vôbec neprekážajú. Keďže ale boli mokré, jedno z detí sa pošmyklo a rozsypalo po celom trávniku lentilky. Voda v kobercoch začala rozpúšťať farebnú cukrovú polevu. Pod každou lentilkou farba z polevy presiakla cez všetky koberce až po trávnik.
Keď si tú hrôzu Marcel všimol, prišlo mu zle. Potom si ale uvedomil, že sa vlastne nič zlé nestalo a začal namiesto toho rozmýšľať, koľko rôznych lentilkových farieb je na každom z kobercov. Je ale veľmi unavený z toľkého úmorného tepovania. Keby mu len niekto s touto úlohou pomohol…
Úloha
Marcel vám povedal, ako rozmiestnil koberce. Koberce sa nepretínajú ani nedotýkajú stranami ani rohmi. Dva koberce môžu byť navzájom nad sebou iba ak je jeden z nich úplne obsiahnutý v druhom a nedotýkajú sa stranami. Teda môže sa stať že je menší pod väčším, ale aj to, že je väčší pod menším a dokonca môže byť celá kopa kobercov medzi nimi (pričom každá dvojica v tejto kope spĺňa tieto pravidlá).
Koberce sú obdĺžnikové a sú poukladané tak, aby ich strany boli rovnobežné s osami \(x\) a \(y\).
Ďalej vám povedal súradnice a farby jednotlivých lentiliek. Farieb môže byť mnoho, no môže byť viac lentiliek tej istej farby.
Vašou úlohou je povedať Marcelovi, koľko rôznych farieb z lentiliek sa dostalo na ktorý koberec.
Formát vstupu
Na prvom riadku vstupu sú dve čísla \(n\) a \(m\) - počet kobercov a počet lentiliek. Platí, že \(1 \leq n, m \leq 10^5\).
Nasleduje \(n\) riadkov. Na \(i\)-tom z nich je popis \(i\)-teho koberca. Tento popis pozostáva zo 4 čísiel \(1 \leq x_1, y_1, x_2, y_2 \leq 10^9\) - súradníc ľavého dolného a pravého horného rohu. Môžete predpokladať, že \(x_1 < x_2\) a tiež \(y_1 < y_2\).
Na \(j\)-tom z ďalších \(m\) riadkov je popis \(j\)-tej lentilky. Pozostáva z 3 čísiel \(1 \leq x, y, f \leq 10^9\) - súradníc lentilky a jej farby.
Formát výstupu
Vypíšte \(n\) riadkov. Na \(i\)-tom z nich bude jedno číslo - počet rôznych farieb, ktoré lentilky pridali na \(i\)-ty koberec.
Hodnotenie
Sú 4 sady vstupov. Platia v nich nasledovné obmedzenia:
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n, m \leq\) | \(1000\) | \(50000\) | \(100\,000\) | \(100\,000\) |
Príklad
Input:
3 3
1 1 10 10
2 2 9 9
4 4 6 8
2 10 1
2 9 2
5 7 3
Output:
3
2
1
Riešenie hrubou silou je jednoduché. Pre každý koberec môžeme mať set
a farbu každej lentilky vložíme do set
u každého koberca, na ktorom sa nachádza. Dostaneme riešenie s časovou zložitosťou \(O(nm \log m)\). Ak namiesto set
u použijeme hešovaciu tabuľku, tak to zlepšíme na \(O(nm)\). Pamäť bude \(O(n + m)\), ak si zapamätáme iba koberce, lentilky a set
y.
Vzorové riešenie
Predstavme si, že by vždy ležal menší koberec na väčšom. Uvedomme si, že toto nijak nezmení odpoveď, pretože farba z lentilky presiakne cez všetky koberce pod ňou bez ohľadu na ich poradie. Môžeme teda predpokladať, že koberce skutočne ležia týmto spôsobom.
Keďže sa koberce nepretínajú stranami, tak nám vzniklo niekoľko kôpok kobercov. Každá z týchto kôpok je v podstate strom. Jeho koreňom je spodný, najväčší koberec.
Poďme si rozmyslieť, ako spraviť, aby sme každú lentilku nemuseli zapisovať do každého koberca, ktorý ofarbí, ale iba do jedného. Zapíšeme ju iba do najvrchnejšieho. To nám stačí, pretože pod ním sú už iba väčšie koberce. Keď zapíšeme všetky lentilky, tak nám bude stačit prejsť každý strom a každému vrcholu, čiže kobercu, priradiť farby tak, že zjednotíme farby všetkých jeho synov. Potlačíme teda farby z listov, kam sme ich zapísali, dohora.
Vieme to spraviť rýchlo? Pre každý koberec môžeme mať set
, do ktorého budeme dávať jeho farby. Keby sme do otca vkladali farby zo synov len tak ledajako, mohlo by sa nám stať, že budeme jednu farbu kopírovať príliš veľa krát. Použijeme teda trik používaný napríklad v dátovej štruktúre union-find
, kde spájame dve množiny tak, že kopírujeme prvky z menšej tabuľky do väčšej. Predstavme si spájanie jedného zo synov s otcom. Ak je viac farieb v otcovi, prekopírujeme farby zo syna do otca. Ak je viac farieb v synovi, prekopírujeme farby z otcovského set
u do synovho a prehlásime ho za nový otcov set
. Takto bude každá lentilka prekopírovaná nanajvýš \(\log m\)-krát. Na tomto mieste sa vieme zbaviť jedného logaritmu tým, že namiesto set
u použijeme hešovaciu tabuľku. Táto časť teda bude mať zložitosť \(O(m \log m)\).
Ostáva nám vyriešiť iba to, ako zapísať každú lentilku iba do najvrchnejšieho koberca. Toto je celkom známa úloha. Budeme mať intervalový strom. Z obdĺžnikov zoberieme začiatočnú a konečnú zvslú úsečku a o každej si zapamätáme, či je začiatočná, alebo konečná. Tieto úsečky si usporiadame podľa \(x\)-ovej súradnice spolu s lentilkami. Usporiadané úsečky pozametáme intervaláčom. Vždy, keď nájdeme začiatočnú úsečku, v intervalovom strome si zapamätáme že daný obdĺžnik je na celom intervale, ktorý pokrýva daná úsečka aktuálne najvyššie. Ináč povedané, na intervale danej úsečky pridáme na stack
korešpondujúci obdĺžnik. Keď dojdeme ku koncu obdĺžnika, odoberieme daný obdĺžnik zo stack
u na celom intervale tejto koncovej úsečky. Keď nájdeme lentilku, pozrieme sa do intervalového stromu, ktorý obdĺžnik je najvyššie na danom mieste a lentilku do neho zapíšeme. Keďže súradnice sú veľké, budeme pre intervalový strom potrebovať spraviť kompresiu súradníc, alebo ho stavať dynamicky. Táto časť bude mať zložitosť \(O((n + m) \log (n + m))\), čo bude aj výsledná časová zložitosť programu. Pamäťová zložitosť bude \(O(n + m)\).
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.