7. Obávaný skok syslí, horizontálno-zvislý vzorové riešenie

4 0 2
5 4 3 1

6

4 1 2
5 4 3 1

4

8 3 3
11 15 15 10 10 7 1 1

14

Hrubá sila

Štedrí vedúci Klubu Slovenských Paraglidistov vám darujú jeden bod za riešenie, ktoré implementuje definíciu zo zadania. Stačí vyskúšať všetky trasy s \(s\) horami a zistiť, ktoré z nich vyhovujú podmienke v zadaní. Tak prečo to nevyužiť? Overíme si, či sme správne pochopili úlohu, a navyše budeme mať správne riešenie na otestovanie svojich riešení pre ďalšie sady.

Potrebujeme už len vymyslieť čo najpríjemnejší spôsob, ktorým trasy dĺžky \(s\) vyskúšame. Zamyslime sa, ako by si mohol za letu trasu zvoliť Syseľ? Vyberie si ľubovolnú horu, na ktorú sa na začiatku postaví a povie si, že chce skočiť ešte \((s-1)\)-krát. Skočí s padákom, pričom letí nad všetkými horami napravo od tejto začiatočnej hory. Keď uvidí horu ktorá je aspoň o \(m+1\) metrov nižšia ako tá z ktorej práve skočil, môže sa rozhodnúť že pristane práve na nej, alebo pokračuje v lete a rozhoduje sa nad ďalšou. Keď na nejakej hore pristane, opakuje sa tento proces znova – ale tentokrát už Syseľ túži skočiť len ďalších \((s-2)\)-krát. Keď napokon pristane na niektorej z hôr a netúži už viac skákať, resp. túži skočiť ešte 0-krát, práve dokončil jednu trasu, ktorá mu vyhovuje.

Táto úvaha sa už celkom príjemne programuje pomocou rekurzie – skúsime ‘skočiť’ z každej hory, pamätajúc, že sme už dokončili trasu dlhú 1. Následne prejdeme všetky hory napravo, a pre každú horu nižšiu o viac ako \(m\) od vybranej hory zavoláme tú istú funkciu (akoby sme stáli na tejto hore) s tým, že sme už preleteli trasu dĺžky 2. Keď na nejakej hore pristaneme a zistíme, že sme už preleteli trasu s \(s\) horami, pripočítame k odpovedi 1.

Na záver malý detail – trás dĺžky \(s\) v pohorí s \(n\) horami môže byť najviac \({n \choose s}\). Toto číslo je v prvej sade najviac \({20 \choose 10} = 184\,756\), a teda nepresiahne hodnotu \(10^9 + 7\). Výsledok teda nemusíme modulovať (počítať zvyšok po delení \(10^9 + 7\)).

Aká je naša pamäťová zložitosť? Stačí nám pamätať si výšky všetkých \(n\) hôr a zopár pomocných premenných. Naša rekurzívna funkcia sa v sebe zavolá najviac \(s\)-krát, a teda počet premenných, ktoré máme vytvorené v ľubovoľnom čase v jej všetkých volaniach bude úmerný \(s\). Celková pamäťová zložitosť je teda \(O(n+s)\).

Ako je to s časovou zložitosťou? Skúšame všetky platné trasy dĺžky \(s\) spomedzi \(n\) hôr. V najhoršom prípade všetky trasy dĺžky \(s\) vyhovujú Sysľovi, a bude ich teda \({n \choose s}\). Pre jednoduchší odhad zložitosti využijeme fakt, že všetkých podmnožín \(n\) prvkov je \(2^n\). Naše riešenie síce zaujímajú len \(s\)-prvkové množiny hôr v našom pohorí, ich počet však rastie asymptoticky rovnako rýchlo. Časová zložitosť je teda exponenciálna od \(n\), s horným rádovým ohraničením \(O(2^n)\).

#include <iostream>

using namespace std;

int hory[20],n,m,s,odpoved = 0;

//Simuluje Sysľa - skúša z hory 'pozicia' pristáť na niektorej ďalšej,
//alebo pripočíta odpoveď ak úspešne dokončil trasu dĺžky s.
void rekurzia(int pozicia,int kolko)
{
    if(kolko==0) // našli sme jednu platnú trasu
    {
        odpoved++;
        return;
    }

    for(int k=pozicia+1;k<n;++k) // skúsime skočit na každú ďaľšiu horu
        if(hory[pozicia]-hory[k]>m)
            rekurzia(k,kolko-1);
}

int main()
{
    cin >> n >> m >> s;
    for(int i=0;i<n;++i) cin >> hory[i];
    //spočítame počet trás dĺžky s začínajúc horou 0,1,...,n-1
    for(int i=0;i<n;++i) rekurzia(i,s-1);

    cout << odpoved << "\n";
    return 0;
}

Postupne predlžujeme známe trasy

Označme výšku \(i\)–tej hory v smere na východ \(h_i\). Pozrime sa bližšie na otázku, ktorú sme sa pri rekurzii pýtali: koľko platných trás dĺžky \(s\) začína v hore \(i\)? Ak by sme odpoveď chceli popísať slovne, je ich práve toľko, koľko platných trás dĺžky \(s-1\) začína v horách \(i+1,i+2,...,n-1\), ktoré sú vysoké najviac \(h_i-m-1\). Keby sme pre každú horu \(k\), pre ktorú platí \(i < k\), vedeli povedať, koľko platných trás dĺžky \(s-1\) v nej začína, ľahko by sme odpoveď spočítali. No a koľko takých trás existuje pre nejakú horu \(k\)? No predsa presne toľko, koľko platných trás dĺžky \(s-2\) začína v takých horách \(k+1,k+2,...,n-1\), ktoré sú vysoké najviac \(h_k-m-1\).

Ale to je tá istá otázka ako predtým! Keby sme vedeli počet platných trás dĺžky \(d\) začínajúc v každej hore v pohorí, pre každú horu \(i\) by sme vedeli sčítať počty platných trás tých hôr, ktoré sú napravo od nás a dostatočne nízke, a tým našli počet platných trás dĺžky \(d+1\) začínajúc v hore \(i\). Túto hodnotu spočítame pre každé \(0 \leq i \leq n-1\). Odteraz budeme označovať počet platných trás dĺžky \(d\) začínajúc v hore \(i\) ako \(v(d, i)\).

Ak teda poznáme \(v(d, i)\) pre nejaké \(d\), vieme teraz spočítať počet platných trás dĺžky \(d+1\) pre každú horu v pohorí! A kde začať? Poznáme pre nejaké \(d\) počet platných trás začínajúc v každej hore? Samozrejme - každá hora je sama o sebe platná trasa dĺžky 1. Vieme teda našou úvahou spočítať pre každú horu \(i\) počet platných trás dĺžky 2 ktoré v nej začínajú – \(v(2,i)\). Jednoducho sčítame \(v(1, j)\) všetkých dostatočne nízkych hôr napravo. Hodnoty \(v(2,i)\) sú všetko, čo potrebujeme na vypočítanie trás dĺžky tri – \(v(3,i)\), a tak ďalej. Tento výpočet zopakujeme teda \((s-1)\)-krát a dostaneme pre každú horu počet platných trás dĺžky \(s\), ktoré v nej začínajú. Tieto čísla sčítame, a máme hľadaný výsledok. Keďže nás zaujíma len jeho zvyšok po delení číslom \(10^9+7\), všetky výpočty ním budeme modulovať.

Na záver tohto riešenia ešte vieme spraviť jedno pozorovanie: akonáhle sme pre každú horu zistili počet platných trás dĺžky \(d+1\) ktoré v nej začínajú (\(v(d+1,i)\),) predtým vypočítaná hodnota \(v(d,i)\) nás už nebude nikdy zaujímať. Na celý výpočet nám teda budú stačiť dve polia, pričom budeme striedať ich význam. Pri prvom výpočte máme v prvom poli hodnoty \(v(d,i)\), a do druhého počítame \(v(d+1,i)\). Následne prvé pole vynulujeme, a spočítame doňho pre každú horu \(v(d+2,i)\), využívajúc výsledky pre \(d+1\) ktoré máme teraz uložené v druhom poli.

Dokopy si teda budeme pamätať výšky všetkých \(n\) hôr, a zároveň dve polia dĺžky \(n\), v ktorých budeme striedavo vypočítavať pre každú horu počet v nej začínajúcich platných trás postupne väčšej dĺžky. Pamäť teda lineárne závisí od \(n\) a ničoho iného – \(O(n)\).

Tú istú úvahu opakujeme \((s-1)\)-krát – máme pre každú horu \(i\) vypočítanú hodnotu \(v(d,i)\) pre nejaké \(d\) (na začiatku \(v(1,i) = 1\)), a pre každú horu budeme počítať \(v(d+1,i)\). Ako vyzerá tento výpočet pre jednu horu? Prejdeme všetky hory východnejšie od nej, a pre každú dostatočne nízku horu \(k\) pripočítame k našej hore jej hodnotu \(v(d,k)\). Toto robíme pre každú horu, ktorých je \(n\), a počet kontrolovaných hôr napravo od nich takisto závisí lineárne od \(n\). Vypočítanie hodnôt pre \(v(d+1,i)\) z hodnôt \(v(d,i)\) nám teda zaberá kvadratický čas od \(n\), a tento výpočet opakujeme \((s-1)\)-krát, teda lineárne od \(s\). Celková časová zložitosť bude teda \(O(s\cdot n^2)\).

#include <iostream>

using namespace std;
int main()
{
    int n,m,s,i,j,k,mod = 1000000007;
    cin >> n >> m >> s;
    int dp[2][n],hory[n];

    for(i=0;i<n;++i)
    {
        cin >> hory[i];
        dp[1][i] = 1; //každá hora je sama o sebe trasa dĺžky 1
    }

    for(i=1;i<s;++i)
    {
        int teraz = i%2, potom = (i+1)%2;
         //vynulujeme riadok kam budeme zapisovať, keďže v ňom sú súčty predošlých trás
        for(j=0;j<n;++j) dp[potom][j] = 0;
        for(j=0;j<n;++j)
        {
            //sčítame počet trás dĺžky i, začínajúc dostatočne nízkymi horami napravo
            for(k=j+1;k<n;++k)
            {
                if(hory[j]-hory[k]>m)
                {
                    dp[potom][j] += dp[teraz][k];
                    dp[potom][j] %= mod;
                }
            }

        }
    }

    int odpoved = 0;
    //sčítame počet trás dĺžky s začínajúc horami 0,1,...,n-1
    for(i=0;i<n;++i)
    {
        odpoved += dp[s%2][i];
        odpoved %= mod;
    }

    cout << odpoved << "\n";

    return 0;
}

Spočítavame rýchlejšie

Potrebujeme si zrýchliť naše riešenie. Zjavne potrebujeme z našej časovej zložitosti odstrániť faktor \(n^2\), keďže pre \(n = 100\,000\) je táto zložitosť neúnosná. Čo nám trvá \(n\) krokov? \(n\)-krát spracúvame nejakú horu \(i\) a počítame počet trás dĺžky \(d+1\) (postupne \(2,3,...,s-1,s\)), ktoré v nej začínajú – \(v(d+1,i)\). Ako vyzerá spracovanie jednej hory? Prejdeme všetky hory východnejšie od nej (teda hory \(k\) kde \(i < k\). Tých je lineárne veľa od \(n\)), a pre tie hory, ktorých výška \(h_k\) je najviac \(h_i - m - 1\) pripočítame k našemu číslu \(v(d+1,i)\) počet trás dĺžky \(d\) začínajúc v hore \(k\) – \(v(d,k)\).

Pozrime sa na hory, ktorých trasy vlastne chceme spočítať. Zoberme si všetky východnejšie hory od hory \(i\), a usporiadajme si ich podľa výšky. Ktoré z nich nás zaujímajú? Tie dostatočne nízke! Presnejšie, tie hory, ktorých hodnoty \(v(d,k)\) chceme spočítať, budú po usporiadaní tvoriť súvislý úsek hôr začínajúci najnižšou z nich, a končiaci najvyššou horou, ktorej výška \(h_k\) je stále menšia ako \(h_i - m\) (toto môžu teda byť aj všetky východnejšie hory od hory \(i\), prípadne ani jedna). Toto pozorovanie nám samo o sebe nepomôže – usporiadať východnejšie hory, ktorých je lineárne veľa od \(n\), vieme najlepšie v čase \(n \log n\). Pomôžeme si však, keď si uvedomíme že nás pri počítaní \(v(d+1,i)\) vlastne nezaujíma, ktorá východnejšia hora prispieva koľkými trasami dĺžky \(d\), ani to, kde tieto hory vlastne sú – stačí vedieť že su dostatočne nízke a východnejšie od nás.

Skúsme na to isť teda trošku inak. Namiesto toho, aby sme zisťovali pre každú horu jej hodnotu \(v(d,i)\), bude nám stačiť pre každú výšku \(h\) súčet \(v(d,i)\) tých hôr \(i\), ktoré majú výšku \(h\). Ak toto vieme, pri počítaní \(v(d+1,i)\) by nám stačilo spočítať tieto hodnoty pre výšky \(1,2,...,h_i-m-1\). Tieto hodnoty si pre hory dostatočne malej výšky môžeme rovno pamätať v pomocnom poli \(P\) na indexoch \(1,2,...,10^6\). Keď si teda náš algoritmus takto pozmeníme, stačilo by nám vedieť sčítavať čísla na intervale v poli \(P\) v lepšom ako lineárnom čase od veľkosti intervalov. Vieme to urobiť?

Odpoveď je: áno. Budeme však musieť použiť dátovú štruktúru, ktorá dokáže spracovávať (v našom prípade sčítavať) hodnoty na zvolenom intervale: intervalový strom. Ak ste o intervalovom strome nepočuli, prečítajte si nasledovný článok v kuchárke KSP.

Nám bude teraz stačiť skutočnosť, že s intervalovým stromom vieme zostrojiť funkciu \(spocitaj(P,l,r)\), ktorá nám vráti súčet políčok v \(P\) od \(l\) po \(r\), v logaritmickom čase od veľkosti stromu. Zároveň vieme zostrojiť aj funkciu \(pridaj(P,i,y)\), ktorá na políčko \(P_i\) pripočíta hodnotu \(y\) taktiež v logaritmickom čase. Po zvýšení políčka \(i\) už bude funkcia spocitaj(\(P,l,r\)) vracať nový, zvýšený výsledok ak \(l \leq i \leq r\),

Postupovať budeme teda rovnako ako pri pomalšom riešení s niekoľkými rozdielmi. Namiesto polí veľkosti \(n\) budeme mať intervalové stromy s o trochu viac ako \(10^6\) políčkami, pričom v intervale \([l,r]\) stromu \(S_d\) budeme mať hodnoty \(v(d,i)\) začínajúc horami s výškami \(l\) až \(r\). Počet platných trás dĺžky \(d+1\) začínajúcich v hore \(i\) vypočítame pomocou \(spocitaj(S_d, 0, h_i - m - 1)\) (nazvime výsledok \(y\)), a pridáme ho do stromu \(S_{d+1}\) pomocou \(pridaj(S_{d+1}, i, y)\).

Ostáva jedna otázka – ako zaručiť, že práve spracovaná hora \(i\) neovplyvní počet spočítaných trás, keď budeme v ďalšom kroku spracovávať východnejšiu horu \(i+1\)? Stačí, ak po vypočítaní hodnoty \(v(d+1,i)\) v \(S_{d+1}\) z nášho momentálne používaného stromu \(S_d\) zmažeme z políčka \(h_i\) počet trás, ktoré začínali v našej hore \(v(d,i)\). Túto hodnotu si môžeme zapamätať v poliach veľkosti \(n\) (v riešení nazvané zacina). Keď spočítame počet trás dĺžky \(d+1\), zapíšeme si do prislúchajúceho poľa túto hodnotu, a tú použijeme pri výpočte \(S_{d+2}\).

Na záver prichádza rovnaké pozorovanie ako pri riešení dynamickým programovaním. Pri výpočte trás s dĺžkou \(d+1\) do intervalového stromu \(S_{d+1}\) a \(zacina_{d+1}\) využívame len výšky hôr a hodnoty v \(S_d\) a \(zacina_d\). Takisto ako minule si teda vystačíme len s dvoma pármi štruktúr, ktoré budeme pri výpočtoch striedať.

Pamätáme si výšky všetkých hôr a počet trás končiacich v každej z nich v (dvoch) poliach zacina , ktoré majú počet prvkov lineárny od \(n\). K tomu nám pribudli dva rovnako veľké intervalové stromy, ktorých veľkosť je lineárna od najvyššej hory na vstupe. Ak by sme toto číslo mali uvedené na vstupe ako \(max\) (a teda rozlišovali sadu 4 od sád 1,2,3), naša pamäťová zložitosť by bola \(O(n+max)\).

Namiesto spočítania trás začínajúc v menších horách napravo v čase lineárnom od \(n\) používame konštantne veľa volaní funkcii pridaj a spocitaj, ktorých časová zložitosť je \(O(\log max)\). Výpočet robíme stále pre všetkých \(n\) hôr a opakujeme \(s\)-krát, postupne pre väčšie dĺžky trás. Vynulovanie polí zacina a intervalového stromu pri prestupovaní z dĺžky \(d\) na \(d+1\) robíme taktiež v lineárnom čase od ich veľkosti. Časová zložitosť je teda \(O(s\cdot n\cdot \log max + max)\).

#include <bits/stdc++.h>

using namespace std;
struct interval
{ int l,r; };
//intervaly[x] nám povie ktoré najľavejšie a najpravejšie políčko je v podstrome x
vector<interval>intervaly;
vector<int>strom[2]; //intervalové stromy
int mod = 1000000007;

//prepočítajú sa hodnoty v strome 'ktory' na ceste z koreňa do 'kde'
void bubli(int ktory,int kde)
{
    if(!kde) return;
    strom[ktory][kde] = (strom[ktory][kde*2] + strom[ktory][kde*2+1]) % mod;
    bubli(ktory,kde/2);
}

//pridá intervalovému stromu 'ktory' na políčko 'kde' hodnotu 'v'
void pridaj(int ktory,int kde,int v)
{
    strom[ktory][kde] += v;
    //pridaním záporného čísla môžeme omylom prejsť k zápornému modulovanému súčtu
    if(strom[ktory][kde]<0) strom[ktory][kde] += mod;
    strom[ktory][kde] %= mod;
    bubli( ktory, (kde)/2 );
}

//spočíta súčet čísel v strome 'ktory' od políčka 'vlavo' po políčko 'vpravo'
int spocitaj(int vlavo,int vpravo,int ktory,int kde)
{
    if(vlavo>vpravo)
        return 0;

    //podstrom 'kde' vie súčet presne nášho intervalu
    if(intervaly[kde].l==vlavo && intervaly[kde].r==vpravo)
        return strom[ktory][kde];
    //v intervale lavého syna nás nič nezaujíma - zavoláme sa do pravého
    else if (intervaly[kde*2].r<vlavo)
        return spocitaj(vlavo,vpravo,ktory,kde*2+1);
    //v intervale pravého syna nás nič nezaujíma - zavoláme sa do ľavého
    else if (intervaly[kde*2+1].l>vpravo)
        return spocitaj(vlavo,vpravo,ktory,kde*2);
    //obaja synovia majú časť intervalu. Zavoláme sa na oboch
    else
        return (spocitaj(vlavo,intervaly[kde*2].r,ktory,kde) + spocitaj(intervaly[kde*2+1].l,vpravo,ktory,kde) ) % mod;

}
int main()
{
    //načítavame veľa čísel - zrýchlyme vstup a výstup
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //MAX je najväčšia výška hory, velkost je počet listov v intervalovom strome
    int MAX = 1000000,n,m,s,i,j,velkost=1;
    cin >> n >> m >> s;

    //zacina[cislo%2][i] bude počet trás dĺžky 'cislo' začínajúc horou i
    int hory[n],zacina[2][n];
    for(i=0;i<n;++i)
    {
        cin >> hory[i];
        zacina[1][i] = 1; //každá hora je sama o sebe trasa dĺžky 1
    }

    while(velkost<MAX) velkost *= 2;

    strom[0].resize(velkost*2,0);
    strom[1].resize(velkost*2);

    //pripočítame trasu dĺžky 1 začínajúc s výškou hory[i]
    for(i=0;i<n;++i)
        pridaj(1,hory[i]+velkost,1);


    intervaly.resize(velkost*2);
    for(i=velkost;i<velkost*2;++i)
        intervaly[i].l = intervaly[i].r = i;
    for(i=velkost-1;i>0;i--)
    {
        //najlavejšie políčko podstromu i je najlavejšie políčko jeho ľavého syna
        intervaly[i].l = intervaly[i*2].l;
        //rovnaká úvaha pre najpravejšie políčko
        intervaly[i].r = intervaly[i*2+1].r;
    }

    for(i=1;i<s;++i)
    {
        int teraz = (i%2),potom = (i+1)%2;
        //vynulujeme strom do ktorého budeme počítať trasy dĺžky i+1
        for(j=1;j<velkost*2;++j)
            strom[potom][j] = 0;
        for(j=0;j<n;++j)
        {
            int index = hory[j]+velkost; //list predstavujúci výšku hory[j]
            //spočítame počet trás dĺžky i začínajúc v horách vysokých najviac hory[j]-m-1
            int sucet = spocitaj(velkost,index-m-1,teraz,1);
            pridaj(potom,index,sucet);
            zacina[potom][j] = sucet;
            /* odčítame zo stromu počet trás, ktoré prispievala naša hora,
            pretože berieme do úvahy len hory napravo od tej ktorú budeme počítať v ďaľšiom kroku */
            pridaj(teraz,index,-zacina[teraz][j]);
        }

    }

    //počet trás dĺžky s začínajúc v ľubovoľnej výške je v koreni stromu[s%2]
    cout << strom[s%2][1] << "\n";

    return 0;
}

Ako na vysoké hory

S doterajším prístupom si na horách veľkosti nad \(10^6\) náš program vyláme zuby. Skúsme si tento problém s vysokými horami posunúť niekam inam – vytvorí nám to asi iný problém, a ten potom skúsime vyriešiť.

Zoraďme si teda hory podľa výšky. Prvej hore povieme, že je najnižšia, akoby s výškou 1. Nájdeme si druhú najnižšiu (ale nie s rovnakou výškou!). Tej povieme, že má výšku 2. Takto postupujeme, až každej hore priradíme novú výšku z rozsahu \([1,n]\). Tieto výšky sa nám už zmestia do intervalového stromu rovnako ako v minulom riešení. Hurá, hotovo!

Teda, skoro. V minulom riešení sme sa opierali o to, že z hory s výškou \(h_i\) vieme skočiť na všetky hory z výškou najviac \(h_i-m-1\), teda súčtom v intervalovom strome cez \(spocitaj(S_d,1,h_i-m-1)\). Toto však už zďaleka nie je pravda. O ozajstných výškových rozdieloch hôr po prečíslovaní už nič nevieme. Hora s novou výškou 2 mohla byť len o jeden meter vyššia ako hora s novou výškou 1, ale rovnako pravdepodobne mohla byť vyššia o miliardu metrov. Po vyriešení veľkosti nášho intervalového stromu teda musíme vyriešiť iný problém – pri spracúvaní hory \(i\) potrebujeme efektívne povedať, ktorá je najvyššia hora ktorá má s \(h_i\) prevýšenie aspoň \(m\). Označme si (novo pridelenú) výšku tejto hory \(inv_i\).

Zoberme si naše hory, ktoré máme momentálne zoradené podľa (starej) výšky. Pozrime sa na tú, ktorá je v strede tohto poľa (nazvime ho \(C\)) – \(C_{n/2}\). Ak je táto hora privysoká – \(h_i-m \leq C_{n/2}\) – určite sú aj hory napravo od nej ( \(C_{n/2 + 1},...,C_{n-1}\) ) príliš vysoké. Ak je však dostatočne nízka – \(h_i-m>C_{n/2}\) určite sú aj všetky hory naľavo od nej ( \(C_0 ,...,C_{n/2-1}\) ) dostatočne nízke. Určite už tušíte riešenie – v poli \(C\) v čase \(O(\log n)\) binárne vyhľadáme najvyššiu horu, ktorá je dostatočne nízka, a zapíšeme si k príslušnej hore \(i\) hodnotu \(inv_i\) – novopriradenú výšku tejto hory (pripomíname, že tá je z rozsahu \([1,n]\)). Toto zopakujeme pre každú horu, pridávajúc nami akceptovanú zložitosť \(O(n\cdot \log n)\).

Už nám zafunguje naše riešenie rovnako ako v minulých sadách – pri počítaní \(v(d+1,i)\) zavoláme spocitaj(\(S_{d+1},0,inv_i\)) a nakoniec odčítame z \(S_d\) na pozící novej výšky hory \(i\) hodnotu \(zacina_i\). Prečíslované výšky hôr si môžeme pamätať napríklad v hešovacej tabulke (map v C++) – jej zložitosť na vkladanie alebo pozeranie sa do nej je \(O(\log k)\), kde \(k\) je počet prvkov v nej – prečíslovanie \(n\) hôr teda bude trvať najviac O(\(n \log n\)) – a pozrieme sa do nej konštantne veľa krát pri spracovaní každej hory počas vypočítavania odpovede.

V pamäti máme teraz \(n\) výšok hôr, dve polia zacina a dva intervalové stromy (ktorých veľkosť po prečíslovaní výšok klesne na \(O(n)\)), a napokon pre každú horu záznam v hešovacej tabuľke a priradenú hodnotu \(inv_i\). Celková pamäťová zložitosť nášho programu je teda \(O(n)\).

Rovnako ako v predchádzajúcom riešení, práca s poliami zacinaj, intervalovými stromami a tentokrát aj s prvkami \(inv_i\) prebieha v lineárnom čase od ich veľkosti, ktorá je lineárna od \(n\). Volania funkcii \(spocitaj\) a \(pridaj\), ktoré obe používame \(O(s\cdot n)\)-krát, je \(O(\log n)\) a teda s celkovou zložitosťou \(O(s\cdot n\cdot \log n)\). Usporiadania poľa \(C\) a prečíslovanie výšok hôr pomocou hešovacej tabulky vieme v vykonať v \(O(n \log n)\), zatiaľ čo \(O(s \cdot n)\) nazretí do nej pri spracovávaní trás intervalovými stromami nám trvá \(O(s\cdot n \cdot \log n)\). Horný odhad časovej zložitosti je teda \(O(s\cdot n\cdot \log n)\).

#include <bits/stdc++.h>

using namespace std;
struct interval
{ int l,r; };
//intervaly[x] nám povie ktoré najľavejšie a najpravejšie políčko je v podstrome x
vector<interval>intervaly;
vector<int>strom[2]; //intervalové stromy
int mod = 1000000007;

//prepočítajú sa hodnoty v strome 'ktory' na ceste z koreňa do 'kde'
void bubli(int ktory,int kde)
{
    if(!kde) return;
    strom[ktory][kde] = (strom[ktory][kde*2] + strom[ktory][kde*2+1]) % mod;
    bubli(ktory,kde/2);
}

//pridá intervalovému stromu 'ktory' na políčko 'kde' hodnotu 'v'
void pridaj(int ktory,int kde,int v)
{
    strom[ktory][kde] += v;
    //pridaním záporného čísla môžeme omylom prejsť k zápornému modulovanému súčtu
    if(strom[ktory][kde]<0) strom[ktory][kde] += mod;
    strom[ktory][kde] %= mod;
    bubli( ktory, (kde)/2 );
}

int spocitaj(int vlavo,int vpravo,int ktory,int kde)
{
    //podstrom 'kde' vie súčet presne nášho intervalu
    if(intervaly[kde].l==vlavo && intervaly[kde].r==vpravo)
        return strom[ktory][kde];
    //v intervale lavého syna nás nič nezaujíma - zavoláme sa do pravého
    else if (intervaly[kde*2].r<vlavo)
        return spocitaj(vlavo,vpravo,ktory,kde*2+1);
    //v intervale pravého syna nás nič nezaujíma - zavoláme sa do ľavého
    else if (intervaly[kde*2+1].l>vpravo)
        return spocitaj(vlavo,vpravo,ktory,kde*2);
    //obaja synovia majú časť intervalu. Zavoláme sa na oboch
    else
        return (spocitaj(vlavo,intervaly[kde*2].r,ktory,kde) + spocitaj(intervaly[kde*2+1].l,vpravo,ktory,kde) ) % mod;

}
int main()
{

    //načítavame veľa čísel - zrýchlyme vstup a výstup
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    long long m;
    int n,s,i,j,velkost=1; //velkost bude počet listov intervalového stromu
    cin >> n >> m >> s;

    long long int hory[n],zacina[2][n],cisla[n+1],inv[n];
    for(i=0;i<n;++i)
    {
        cin >> hory[i];
        cisla[i] = hory[i];
        zacina[1][i] = 1;
    }
    //pridáme zarážku, ktorá bude tvoriť inverziu s každým prvkom
    cisla[n] = (long long)-1000000000000000047;
    sort(cisla,cisla+n+1);
    int pocet = 1;
    //prečíslujeme výšky hôr na rozumne malé čísla
    map<long long int,int> kompresia;
    kompresia[ cisla[0] ] = 0;
    for(i=1;i<=n;++i)
        if(cisla[i]!=cisla[i-1])
        {
            kompresia[ cisla[i] ] = pocet;
            pocet++;
        }

    //pre každú horu binárne vyhľadáme, ktorá v poradí hora s ňou tvorí dostatočne veľkú inverziu
    for(i=0;i<n;++i)
    {
        int lo = 0,hi = n+2;
        while(hi-lo>1)
        {
            int mid = (lo+hi)/2;
            if(hory[i]-m>cisla[mid]) lo = mid;
            else hi = mid;
        }
        inv[i] = kompresia[ cisla[lo] ];
    }

    while(velkost<pocet) velkost *= 2;

    strom[0].resize(velkost*2,0);
    strom[1].resize(velkost*2);
    //pripočítame trasu dĺžky 1 začínajúc s výškou hory[i]
    for(i=0;i<n;++i)
        pridaj(1,kompresia[ hory[i] ]+velkost,1);

    intervaly.resize(velkost*2);
    for(i=velkost;i<velkost*2;++i)
        intervaly[i].l = intervaly[i].r = i;
    for(i=velkost-1;i>0;i--)
    {
        //najlavejšie políčko podstromu i je najlavejšie políčko jeho ľavého syna
        intervaly[i].l = intervaly[i*2].l;
        //rovnaká úvaha pre najpravejšie políčko
        intervaly[i].r = intervaly[i*2+1].r;
    }

    for(i=1;i<s;++i)
    {
        int teraz = (i%2),potom = (i+1)%2;
         //vynulujeme strom do ktorého budeme počítať trasy dĺžky i+1
        for(j=1;j<velkost*2;++j)
            strom[potom][j] = 0;
        for(j=0;j<n;++j)
        {
            int index = kompresia[ hory[j] ] + velkost; //list predstavujúci výšku hory[j]
            /* spočítame počet trás dĺžky i začínajúc v horách nie vyšších ako tou,
               s ktorou tvorí hory[j] dostatočne veľkú inverziu */
            int sucet = spocitaj(velkost,inv[j]+velkost,teraz,1);
            pridaj(potom,index,sucet);
            zacina[potom][j] = sucet;
            /*odčítame zo stromu počet trás, ktoré vytvárala naša hora,
            pretože berieme do úvahy len hory napravo od tej ktorú budeme počítať v ďaľšiom kroku */
            pridaj(teraz,index,-zacina[teraz][j]);
        }

    }

    //počet trás dĺžky s začínajúc v ľubovoľnej hore je v koreni stromu[s%2]
    cout << strom[s%2][1] << "\n";

    return 0;
}