Zadanie

Záhradník Adam sa jedného dňa zobudil a zistil, že zdedil obrovské pole. Pole to nebolo len také, bolo to pole iné, bolo to pole veľké, priam rozsiahle a na Adamove prekvapenie nebolo uložené v počítači, ale jednalo sa o poriadne pole, s traktormi, hnojiskami a zavlažovačmi.

Tak sa Adam rozhodol že bude teda poriadne záhradníčiť.

Prvý krok je inšpekcia pôdy.

Na poli je \(n\) zavlažovačov, ktoré sú vskutku atypické – každý zavlažovač je natočený do jedného zo štyroch smerov (doprava dole, doprava hore, doľava dole alebo doľava hore) a rovnomerne zavlažuje všetku plochu v rohu na ktorý je natočený. Rôzne zavlažovače zavlažujú s rôznou intenzitou. Zavlažovače sú fixne zabudované v poli a Adam s nimi nevie hýbať.

Adam má \(m\) miest na poli, kde by chcel začať pestovať. Avšak najskôr by potreboval vedieť, ako veľmi zavlažované jednotlivé miesta sú. Pomôžte mu!

Úloha

Na poli je \(n\leq 100\,000\) zavlažovačov, a \(m\leq 20\,000\) miest ktoré Adama zaujímajú.

Každý zavlažovač má danú pozíciu na poli, smer a intenzitu. Zavlažovač zavlažuje tú čast poľa na ktorú je nasmerovaný. Ak je napríklad zavlažovač na pozícii (0,0) a je nastavený doprava-hore, zavlažuje všetky políčka s nezápornými súradnicami.

Vlaha na pozícii je súčet intenzít všetkých zavlažovačov zavlažujúcich túto časť poľa.

Pre všetky miesta, ktoré Adama zaujímajú zistite, aká je ich vlaha.

Navyše, v niektorých sadách by chcel Adam vedieť odpovede ihneď - predtým ako sa spýta ďalšiu otázku. Na získanie plného počtu bodov musí váš program vedieť odpovedať online.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(n\) (\(1 \leq n \leq 100\,000\)).

Na ďalších \(n\) riadkoch sú medzerou oddelené čísla \(x_i\), \(y_i\) – pozície \(i\)-teho zavlažovača, \(v_i\) – intenzita \(i\)-teho zavlažovača a ukazovateľ smeru. “DP” znamená dole-pravo, \(DL\) je dole-ľavo, \(HL\) je hore-ľavo a \(HP\) je hore-pravo.

Nasledujú dve medzerou oddelené celé čísla \(m\) (\(1\leq m\leq 20\,000\)) – počet miest, ktoré zaujímajú Adama, a \(k\) (\(0\leq k\leq 1\)).

Nasleduje \(m\) riadkov, na každom z nich sú dve medzerou oddelené čísla, \(x\) \(y\). Ak \(k = 0\), potom pozície miesta sú \(x\) \(y\).

Ak \(k = 1\), nech \(a\) je vlhkosť predchádzajúceho miesta. Potom súradnice sú \(x \oplus a\) \(y\oplus a\), kde \(\oplus\) je bitový xor.

Pozície miest a zavlažovačov sa môžu zhodovať. Dva zavlažovače sa môžu nachádzať na rovnakom mieste.

Všetky súradnice v absolútnej hodnote nepresahujú \(10^9\). Všetky intenzity sú celé čísla v rozsahu \(1\)\(10^4\).

Formát výstupu

Vypíšte \(m\) riadkov, na každom z nich vlahu na \(i\)-tom mieste, v poradí v akom boli zadané na vstupe.

Hodnotenie

Existuje \(8\) testovacích sád, každá za jeden bod.

V prvých dvoch sadách sú všetky súradnice medzi \(0\) a \(1000\).

V prvej a tretej sade platí, že \(m, n \leq 1000\).

V štvrtej a piatej sade navyše platí, že všetky súradnice sú medzi \(0\) a \(10^5\).

Vo všetkých sadách okrem siedmej a ôsmej platí \(k = 0\).

Príklady

Input:

5
-1 -1 1 DL
-1 1 2 HL
1 -1 4 DP
1 1 8 HP
0 1 3 DP
7 0
-100 100
0 1
2 1
-1 0
0 -5
2 -2
-1000000000 -1000000000

Output:

2
3
11
0
3
7
1

Input:

5
-1 -1 1 DL
-1 1 2 HL
1 -1 4 DP
1 1 8 HP
0 1 3 DP
2 1
-100 100
2 3

Output:

2
3

*Pozície zavlažovačov a miest sú rovnaké ako v prvom vstupe. Lenže v tomto prípade je \(k = 1\).

Hrubá sila

Keby mal Adam veľa času a trpezlivosti, mohol by na riešenie ísť hrubou silou: vždy, keď ho začne zaujímať nejaké miesto, pre každý zavlažovač samostatne skontroluje či miesto zavlažuje. To vie zistiť v konštantom čase.

Takto vie zistiť vlahu všetkých miest v \(O(nm)\) čase a \(O(n)\) pamäti.

Žiaľ, hrubá sila stačí len na prvú a tretiu sadu.

Malé pole

Čo ak je Adamove pole malé? Potom by si Adam mohol spočítať odpoveď pre každé miesto na poli, a potom vie odpovedať na otázku o akomkoľvek mieste, ktoré by ho mohlo zaujímať.

Ako to vie spočítať? Mohol by napríklad použiť 2D prefixové súčty. Viac o tom, ako ich viete použiť sa už dozviete v KSP kuchárke.

Presnejšie, Adam si chce spraviť prefixové súčty pre každý zo štyroch smerov, a vlahu na mieste záujmu potom dostane ako sumu vláh zo všetkých smerov. Toto vie Adam spočítať v časovej zložitosti \(O(m + n + (\max(x_i, y_i))^2)\), a v pamäti \(O((\max(x_i, y_i))^2)\).

K rýchlemu riešeniu

Hrubá sila očividne nestačí. Skúsme sa najskôr zamyslieť nad prípadom, že všetky zavlažovače sú orientované rovnako. Pozrime sa na miesto ktoré Adama momentálne zaujíma. Ktoré zavlažovače ho zasahujú?

Ako môžme vidieť na ilustračnom obrázku, vyznačené miesto (červeným) zavlažujú všetky zavlažovače v červenom rohu, takže aby sme rýchlo zistili vlahu, chceli by sme vedieť zistiť rýchlo spočítať sumu vláh zavlažovačov umiestnených v danom rohu. Skúsenejšiemu riešiteľovi už možno niečo hovorí, že by sa Adamovi zišiel intervalový strom.

Vieme miesta vopred

Na prvý pohľad by to mohlo vyzerať, že bude treba dvojrozmerný intervalový strom, ale ukáže sa, že ten vôbec netreba. Najskôr sa pozrime na prípad, že Adam vie, ktoré miesta ho zaujímajú vopred.

Zoberme si prípad, že všetky zavlažovače smerujú hore a doprava (ako na obrázku hore). Utrieďme si ich v smere x-súradnice (zľava doprava), a utrieďme si tiež všetky miesta v smere x-súradníc. Potom postupne prechádzajme miesta a zavlažovače zľava doprava a udržujme si dátovú štruktúru, ktorá nám bude hovoriť, pre každú y-súradnicu, koľko je suma vláh zo všetkých zavlažovačov, ktoré sme videli doteraz, na tejto súradnici. Všimnime si (ak sú všetky orientované hore a doprava), že pokiaľ máme spracované všetky zavlažovače naľavo alebo s rovnakou x-súradnicou ako miesto, ktoré nás zaujíma, tak potom vlaha na mieste záujmu je suma vláh všetkých spracovaných zavlažovačov s y-pozíciou menšou alebo rovnou ako miesto záujmu.

Takže nám na efektívne riešenie stačí vedieť spočítať a aktualizovať sumy na intervaloch. To ide napríklad intervalovým stromom.

Veľmi veľké pole

Ak by sme si chceli v intervalovom strome pamätať vlahy na všetkých y-súradniciach, potom nám riešenie zaberie \(O((n+m)\log\max_i y_i + \max_i y_i)\) času a \(O(n + m + \max_i y_i)\) pamäte. Pre pole veľkosti \(10^9\) nám to nestačí.

Ako to zlepšiť? Všimnime si, že nás zaujíma iba relatívna pozícia zavlažovačov a miest, a tých je málo. Teda si zmeňme súradnicovú sústavu pomocou kompresie súradníc. To znamená, utrieďme si všetky x a y súradnice na vstupe, a potom zmenňme súradnice vstupu tak, že najmenšia x-súradnica sa zmení na 0, druhá najmenšia na 1, atď. Takto sa nám zmenší počet y-súradníc ktoré nás zaujímajú na dostatočne málo a dostaneme (offline) riešenie v čase \(O((n+m)\log n)\) a pamäti \(O(m+n)\).

Online riešenie

Čo ak nám miesta prichádzajú postupne?

Nevieme použiť predchádzajúce riešenie: miesta nám neprichádzajú utriedene, potrebovali by sme sa vedieť “dostať” ku intervalovému stromu v rôznych časoch, napríklad “po pridaní všetkých zavlažovačov s x-súradnicou menšou než \(5462\)”.

Alebo by sme to mohli urobiť? Ukazuje sa že áno, riešením je perzistentný intervalový strom. Vysvetlenie ako na perzistentný intervaláč vám nechávam napríklad v tomto videovzoráku.

Riešenie pomocou perzistentného intervaláča funguje v čase \(O((m+n)\log n)\) a v pamäti \(O(n\log n)\) a dá vám plný počet bodov.

Čo s inými smermi?

Pozorný čitateľ ešte zbystrí: hovorím, že už máme riešenie, ale starali sme sa zatiaľ len o jeden smer? Veď zavlažovače vedia byť aj inak orientované!

Ukáže sa, že nám stačí roztriediť si zavlažovače do skupín podľa smeru zavlažovania, a pre každý mať separátny intervaláč. Riešenie vieme použiť pre každý smer rovnaké, len si je treba situáciu vhodne rotovať. Toto nám pridá do časovej a pamäťovej zložitosti iba konštantný faktor.

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ť.