Naivná dynamika

Definujeme $dp[i][j]$ ako maximálny počet spojení, ak posledná dvojica, ktorú sme vybrali je $(i, j)$ (príslušné čísla stromov sú $(p_i, q_j$)). Ak dvojicu $(i, j)$ nie je možné vybrať ($|p_i-q_j| > 4$), definujeme $dp[i][j]$ ako $0$. Teraz je odpoveď jednoducho maximum $dp[i][j]$ spomedzi všetkých $(i, j)$.

Ako spočítať $dp$? Prejdeme vzostupne všetky $i$ od $1$ po $n$ a pre každé $i$ prejdeme všetky $j$ od $1$ po $n$. Ak $|p_i-q_j| > 4$, tak $dp[i][j] = 0$. Inak vyskúšame všetky možné predošlé dvojice, teda $(k, l)$ také, že $k < i, l < j$. Odpoveď je jednoducho $dp[i][j] = 1+ \max \lbrace dp[k][l] \rbrace$. Časová zložitosť je $O(n^4)$ (máme $n^2$ stavov a každý spracujeme v $O(n^2)$).

Vylepšená dynamika

Dvojice $(i, j)$, ktoré spĺňajú $|p_i - q_j| \leq 4$ volajme validné. Všimnime si, že validných dvojíc je v skutočnosti málo. Pre každé $i$ je ich najviac $9$, celkovo teda $O(n)$. To znamená, že vieme vyššie popísaný algoritmus vylepšiť hneď dvoma spôsobmi: - môžeme zredukovať počet stavov v našom dynamickom programovaní – stačia nám stavy zodpovedajúce validným dvojiciam; - pri počítaní $dp$ nám stačí kontrolovať menej možných predošlých dvojíc.

Na začiatku si vygenerujeme všetky validné spojenia. Toto vieme spraviť v čase $O(n)$ (napríklad priamočiaro za pomoci poľa $q_{inv}$ takého, že $q_{inv}[q_j] = j$.) Validné spojenia si očíslujeme od $1$ po $S$. Pre $s \in \lbrace 1, \dots, S\rbrace$ definujeme $dp[s]$ ako najväčší počet spojení, ktorý vieme dosiahnuť, ak posledné vybrané spojenie je $s$.

Ako spočítať $dp$? Prechádzame cez všetky validné spojenia s číslom $\tilde{s} \in \lbrace 1, \dots, S \rbrace$. Skontrolujeme, či je spojenie $\tilde{s}$ naľavo od $s$ (ak spojeniu $s$ zodpovedá $(i, j)$ a spojeniu $\tilde{s}$ zodpovedá $(\tilde{i}, \tilde{j})$, tak kontrolujeme, či $\tilde{i} < i$ a zároveň $\tilde{j} < j$ ). Potom $dp[s] = 1 +$ maximum z príslušných hodnôt $dp[\tilde{s}]$. Časová zložitosť sa zlepšila na $O(n^2)$ (máme $O(n)$ stavov a každý spracujeme v $O(n)$).

Vzorová dynamika

Kľúč k úspechu je zapracovať na počítaní $dp[s]$ pre konkrétne $s$. Validné dvojice budeme prechádzať v zotriedenom poradí, po skupinkách: najprv spracujeme tie, ktoré majú $i = 1$, potom tie s $i = 2$, atď. Vďaka tomuto bude jednoduché overovať, či $\tilde{i} < i$. Pri počítaní $dp[s]$ potrebujeme preveriť všetkých kandidátov na predošlú dvojicu. Kto sú reálni kandidáti? Sú to presne všetky validné dvojice $\tilde{s}$ s $(\tilde{i}, \tilde{j})$ z predošlých skupiniek ($\tilde{i} < i$), pre ktoré $\tilde{j} < j$. Potrebujeme zobrať maximum z hodnôt $dp[\tilde{s}]$ pre týchto kandidátov. Na takéto veci je ako stvorený intervalový strom.

Vytvoríme si intervaláč, v ktorom si pre fixné $\tilde{j}$ od $1$ po $n$ budeme udržovať maximálne $dp[\tilde{s}]$ pre validné dvojice $\tilde{s}$ zodpovedajúce $(\tilde{i}, \tilde{j})$ pre $\tilde{s}$ zo skupiniek, ktoré sme už spracovali. (Ak teda práve spracovávame skupinku s nejakým fixným $i$, tak hodnota v intervaláči pre fixné $\tilde{j}$ bude maximum z hodnôt $dp$ pre validné dvojice spomedzi $(1, \tilde{j}), \dots, (i-1, \tilde{j})$). Intervaláč budeme updatovať vždy po spracovaní celej skupinky. Takýchto updatov bude po každej skupinke najviac $9$ (toľko najviac dvojíc je v jednej skupinke) a intervaláč ich vykoná v $O(\log n)$. No a pri spracovaní konkrétnej dvojice $s$ zodpovedajúcej $(i, j)$ nám vlastne stačí spočítať maximum hodnôt na intervale $[0, j-1]$. Takéto otázky nám intervaláč zodpovie tiež v $O(\log n)$.

Celková časová zložitosť tak bude $O(n \log n)$ (prejdeme $O(n)$ skupiniek, každú spracujeme v $O(\log n)$). Pamäťová zložitosť bude $O(n)$.

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;

#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define FOR(i, x) for(auto &i : x)
#define pb push_back

struct Intervalac {
    int offset;
    vector<int> pole;

    Intervalac(int N) {
        offset = 1;
        while(offset <= N) offset *= 2;
        pole.resize(2*offset, 0);
    }

    void update(int poz, int hod) {
        int v = poz+offset;
        while(v != 0) {
            pole[v] = max(pole[v], hod);
            v /= 2;
        }
        return;
    }

    int maxi(int a, int b, int v, int l, int r) {
        if(l >= b || r <= a) return 0;
        if(a <= l && r <= b) return pole[v];
        return max(maxi(a, b, 2*v, l, (l+r)/2), maxi(a, b, 2*v+1, (l+r)/2, r));
    }

    int maxi(int a, int b) {
        return maxi(a+offset, b+offset, 1, offset, 2*offset);
    }
};

int main() {
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<int> poz(N);
    REP(n, 0, N) {
        int id;
        cin >> id;
        id--;
        poz[id] = n;
    }
    Intervalac Inter(N);
    int vys = 0;
    REP(n, 0, N) {
        int id;
        cin >> id;
        id--;
        vi hrany, hod;
        REP(jd, max(0, id-4), min(N, id+5)) hrany.pb(jd);
        FOR(jd, hrany) {
            hod.pb(1+Inter.maxi(0, poz[jd]));
            vys = max(vys, hod.back());
        }
        REP(i, 0, hrany.size()) {
            int jd = hrany[i];
            Inter.update(poz[jd], hod[i]);
        }
    }
    cout << vys << "\n";
    return 0;
}