BVS a AVL

Pro potřeby tohoto zadání budeme zkratkou BVS označovat obyčejný binární vyhledávací strom, ve kterém se nevyvažuje a v jehož uzlech se neudržuje žádná další informace o jeho tvaru nebo velikosti podstromů.

Je dána posloupnost celých nezáporných hodnot P = a0, a1, ..., aM−1, aM, aM+1, ..., aM+N−1, kde M > 1, N > 1, jsou daná celá čísla.
Dále jsou k dispozici dva BVS, označme je A, B a dva AVL stromy, označme je C, D. Všechny čtyři stromy jsou na začátku prázdné.

Provedeme následující akci. Do stromu A vložíme postupně v roli klíčů hodnoty a0, a1, ..., aM−1, v tomto pořadí, do stromu B vložíme postupně v roli klíčů hodnoty aM, aM+1, ..., aM+N−1 také v tomto pořadí. Poté všechny uzly ze stromu B přesuneme do stromu v pořadí postorder tak, že nejprve v každém uzlu X stromu B přesuneme do stromu A všechny uzly v levém podstromu X, poté do A přesuneme všechny uzly v pravém podstromu X a nakonec do A přesuneme X. Přesun uzlu s klíčem Y znamená smazání tohoto uzlu ve stromu B a vložení klíče Y pomocí operace Insert do stromu A. Konkrétní mechanizmus přesunu je celkem nedůležitý. Významné ale je, že popsaný postup určuje jednoznačně výsledný tvat stromu A stejně tak i tvar stromů A a B v každé fázi celé akce. Při vkládání dodržujeme pravidla operace Insert pro BVS.
Stanovíme cenu celé akce.
Cena operace Insert při vložení uzlu X do BVS (A nebo B) je rovna počtu uzlů na cestě z kořene do uzlu X, přičemž se do cesty vždy započítávají i krajní uzly. Cena za vložení kořene do prázdného stromu je tak 1, cena za vložení dalšího uzlu je 2, atd. S danými daty lze jednoznačně určit cenu celé akce vybudování stromů A a B a následného přesunu všech uzlů z B do A. Cena je rovna součtu cen všech provedených operací Insert v obou stromech.

Nyní provedeme druhou akci zcela analogicky. V roli stromů A a B budou vystupovat stromy C a D, přičemž operace Insert bude probíhat podle pravidel pro AVL stromy, to jest s průběžným vyvažováním, pokud je ho zapotřebí.

Cenu operace Insert při vložení uzlu X do AVL stromu určíme následujícím způsobem.
Pokud po vložení uzlu X do stromu nedojde k rotaci, je cena operace Insert rovna dvojnásobku počtu uzlů na cestě z kořene do uzlu X, přičemž se do cesty vždy započítávají i krajní uzly. Cena za vložení kořene je tak 2, za vložení dalšího uzlu 4, atd.

Pokud po vložení uzlu X do stromu nastane rotace, jednoduchá nebo dvojitá, určíme cenu operace Insert takto: Označme T ten uzel stromu, v němž je detekována nutnost provést rotaci. Cena operace Insert je pak rovna počtu uzlů na cestě z kořene do uzlu X plus počet uzlů na cestě z uzlu T do uzlu X, Obě cesty se měří po vložení uzlu X do stromu a před zahájením rotace/rotací a v obou se započítávají oba krajní uzly.

Stejně jako v předchozím případě nás bude zajímat cena vybudování stromů C a D a následného přesunu všech uzlů z D do C a stejně jako v předchozím případě je cena rovna součtu cen všech operací Insert v obou stromech C a D.

Posloupnost P je dána takto:
a0 = 519217,
ai+1 = (754043 * ai + 500009) mod 1000003 pro i ≥ 0.

Vstup

Na vstupu je jediný řádek s dvěma celými čísly M a N v tomto pořadí, oddělenými mezerou, obě čísla jsou v rozsahu 2 .. 50000.

Výstup

Na výstupu je jeden řádek se dvěma celými čísly oddělenými mezerou. První udává cenu popsané akce pro stromy A a B, druhé udává cenu analogické akce pro stromy C a D,

Příklad 1

Vstup:
2 2
Výstup:
11 22

Příklad 2

Vstup:
2 4
Výstup:
23 51

Příklad 3

Vstup:
5 3
Výstup:
29 54

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data