Zadanie

Vitajte, vitajte! Počula som, že v Legolande ste prvý raz. Nevadí, vysvetlím vám, ako to tu funguje. Je to vskutku celkom jednoduché. Vidíte? Tam pred vami v jednom rade sú všetky atrakcie, ktoré tu máme. Určite ich chcete všetky navštíviť. Ale počkať, ešte som neskončila. Čo prosím? Že zem je hrboľatá? To nie, to len stojíte na legokocke. Ľahko viete skočiť na inú. Samozrejme, skočiť možte len na kocku, ktorá je hneď vľavo, vpravo, hore alebo dole voči vašej momentálnej kocke. Takto si budete hopkať aj medzi našími atrakciami. A teda, medzi dvoma atrakciami vždy prejdete Manhattanskú vzdialenosť. A teraz k pravidlám vašej návštevy. Sú len dve. Prvé: atrakcie, ktoré navštívite musia tvoriť súvislý úsek. Druhé: (pre dobro rodičov, ktorí sa snažia prejsť z atrakcie A do atrakcie B, bez toho, aby prešli okolo atrakcie C (vraj to ušetrí veľa detských sĺz), pre každú trojicu z úseku musí platiť, že súčet vzdialeností medzi dvoma dvojicami sa nemôže rovnať vzdialenosti medzi treťou dvojicou. To je celé. Jednoduché, však? Vyberte si úsek atrakcií, ktoré chcete navštíviť a do toho! Počet úsekov, z ktorých si môžete vybrať je… Vlastne, nemôžem robiť všetkú robotu za vás. Určite na to zvládnete prísť sami.

Úloha

Dané je pole \(R\) s \(n\) atrakciami: \(r_{1}, r_{2}, ..., r_{n}\). Súradnice \(i\)-tej atrakcie sú \((i, r_{i})\). Vzdialenosť medzi atrakciou \(a\) = \((a, r_{a})\) a atrakciou \(b\) = \((b, r_{b})\) je: \(v(a,b)\) = \(|a - b| + |r_{a} - r_{b}|\). Vašou úlohou je nájsť počet súvislých úsekov pre ktoré platí, že v nich neexistuje trojica atrakcií i, j, k, pre ktoré platí \(v(i,j) = v(i,k) + v(k,j)\).

Formát vstupu

V prvom riadku vstupu je číslo \(n\) udávajúce počet atrakcií v poli. V prvej sade platí \(1 \leq n \leq 30\) a v druhej sade platí \(1 \leq n \leq 2 \cdot 10^5\). V nasledujúcom riadku je \(n\) čísel reprezentujúcich ypsilonové súradnice atrakcií \(r\): \(r_{1}, r_{2}, ...,r_{n}\). Pre obe sady platí \(1 \leq r_i \leq 10^9\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo: počet súvislých úsekov, ktoré môžte v Legolande navštíviť.

Príklad

Input:

4
3 5 2 4

Output:

10

V prvom prípade je jedno, ktorý úsek vyberiete. Všetky sú dobré. že prejdeme okolo tretej. Všetky súvislé úseky sú dobré.

Input:

5
7 10 2 10 7

Output:

12

V druhom prípade si môžte všimnúť, že okolo úseku [r_1, r_2, r_3, r_4] nemôžete prejsť, lebo by sa nám mohlo stať, že pri prechode od prvej atrakcie k štvrtej by ste prešli okolo druhej.

Prvé dôležité pozorovanie pre riešenie tejto úlohy je uvedomiť si, aké vlastnosti má trojica, ktorá sa v úseku nemôže nachádzať. Keď sa v Legolande hýbeme medzi dvoma atrakciami, bez ujmy na všeobecnosti si vieme povedať, že pri prechode z atrakcie číslo \(i = (i, r_i)\) k atrakcii číslo \(k = (k, r_k)\) musíme spraviť \(d = k-i\) horizontálnych skokov a \(v = max(r_i,r_k) - min(r_i,r_k)\) vertikálnych skokov. Poradie, v ktorom však týchto \(d\) skokov doprava/doľava a \(v\) skokov hore/dole spravíme môže byť ľubovoľné. To znamená, že ak si nakreslíme obdĺžnik tak, že atrakcie \(i\) a \(k\) sú jeho protiľahlé rohy, môžme si vybrať kombináciu skokov tak, že vieme navštíviť každý bod v tomto obdĺžniku.

Teda pre trojicu atrakcií \(i, j, k\), platí \(v(i,k) = v(i,j) + v(j,k)\), ak atrakcia \(j\) leží v obdĺžniku, ktorého protiľahlé vrcholy sú atrakcie \(i\) a \(k\) (pri predpoklade, že sú v tomto poradí aj usporiadané).

Formálne \(i < j < k\) a zároveň \(min(r_i,r_k) \leq r_j \leq max(r_i,r_k)\).

Z tohto vieme usúdiť, že atrakcie \(i\), \(j\) a \(k\) môžu tvoriť zlú trojicu len v dvoch prípadoch. Buď ich ypsilonové súradnice musia tvoriť nerastúcu podpostupnosť alebo neklesajúcu podpostupnosť v rámci nami vybratého úseku. Ak teda chceme aby atrakcie \(i\), \(j\) a \(k\) netvorili zlú trojicu, musí pre ne platiť, že atrakcia, ktorá sa nachádza horizontálne v strede (\(j\)) musí byť vertikálne buď najvyššie, alebo najnižšie zo všetkých troch atrakcií. Formálne, ak sa atrakcia \(j\) nachádza v strede, musí platiť \(r_i, r_k < r_j\) alebo \(r_i, r_k > r_j\). V opačnom prípade budú určite tvoriť zlú trojicu. Toto môžme generalizovať a povedať, že každá atrakcia v úseku, ktorá je obklopená aspoň jednou atrakciou aj zprava aj zľava sa musí nachádzať vrámci celého úseku vertikálne buď najvyššie alebo najnižšie zo všetkých atrakcií. V opačnom prípade, keď nie je ani najvyššie, ani najnižšie, bude v úseku na jednej strane iná atrakcia vyššie (alebo zarovno) a na druhej iná atrakcia nižšie (alebo zarovno). Tieto tri atrakcie by tvorili zlú trojicu.

Veľmi hrubá sila

Bruteforce riešenie tohoto problému spočíva v prechádzaní všetkých úsekov a skontrolovaní všetkých trojíc v každom úseku.

Počet úsekov dĺžky \(\geq 3\) je \(O(n^2)\) a v každom úseku je \(O(d^3)\) trojíc ktoré treba skontrolovať, kde \(d\) je dĺžka úseku. Horný odhad je teda \(O(n^5)\).

Nemusíme si pritom pamätať nič okrem bodov na vstupe, pamäťová zložitosť je teda \(O(n)\).

Zaujímavá myšlienka

Poďme sa pozrieť, aké dlhé môžu byť úseky, v ktorých sa zlá trojica nenachádza. Je očividné, že úseky dĺžky 1 a 2 určite zlú trojicu obsahovať nebudú a teda všetky tieto úseky môžme rovno zarátať k výsledku. Pri úsekoch dĺžky 3 je už možné, že 3 vrcholy v úseku budú tvoriť neklesajúcu alebo nerastúcu postupnosť vtedy, keď sa stredná atrakcia nachádza vertikálne medzi zvyšnými atrakciami. Zároveň však vieme jednoduhco nájsť prípad, kedy úsek dĺžky 3 neobsahuje zlú trojicu a môžme ho prirátať k výsledku - t.j. keď je stredná atrakcia najvyššie alebo najnižšie. To znamená, že úseky dĺžky 3 musíme prejsť a skontrolovať, aby sme vedeli, či zlú trojicu obsahujú.

Poďme sa pozrieť na úseky dĺžky 4. V tomto prípade sa v úseku nachádzajú presne dve atrakcie, ktoré sú obklopené inými atrakciami z oboch strán a môžu byť stredom zlej trojice. No zároveň stále existuje situácia, keď jedna z týchto atrakcií je v rámci úseku najvyššie a druhá najnižšie a vtedy je celý úsek bez zlej trojice a môže byť prirátaný k výsledku. To znamená, že aj všetky úseky dĺžky 4 musíme po jednom prejsť a osobitne skontrolovať.

Poďme sa pozrieť na úseky dĺžky 5. V tomto prípade sa v úseku už nachádzajú 3 atrakcie, ktoré sú obklopené z oboch strán. Ak každá obklopená atrakcia musí byť buď najvyššie alebo najnižšie, prichádzame k sporu. Ak napríklad druhú atrakciu necháme nachádzať sa najvyššie a tretiu najnižšie, štvrtá atrakcia sa už nebude mocť nachádzať ani najvyššie, ani najnižšie. Môžme teda povedať, že úseky dĺžky 5 (a viac) nemusíme kontrolovať, lebo budú vždy obsahovať zlú trojicu.

Vzorové riešenie

Vzorové riešenie teda len využije toto pozorovanie - stačí manuálne overiť všetky trojice v úsekoch dĺžky 3 a 4 na zistenie, či sú úseky dobré alebo zlé, a prirátať počet úsekov dĺžky 1 a 2, ktoré sú určite dobré.

Prejdenie úsekov má časovú zložitosť \(O(n)\) a skontrolovanie všetkých trojíc v úsekoch dĺžky 3 a 4 má časovú zložitosť O(1). Teda časová zložitosť nášho riešenia je \(O(n)\).

Zároveň si stále nemusíme pamätať okrem bodov a konštantne veľa pomocných premenných nič naviac, pamäťová zložitosť je teda \(O(n)\).

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