8. O()kúzlení vzorové riešenie

5
00001
6
1
2 1 2
1
2 1 1
2 4 4
1

5
3
4

Ako získať ľahké body

V piatich z ôsmich testovacích sád platilo, že \(n\cdot q \leq 1\,000\,000\). To znamená, že pri každej otázke môžeme prejsť celým poľom, v ktorom si pamätáme, pod ktorým pohárikom sa nachádza gulička a niečo s ním spraviť. Toto nám dáva takú voľnosť, že sa úloha blíži obtiažnosťou k úlohe číslo 4. Preto, ak ste nezískali za túto úlohu žiadne body, zoberte si to ako ponaučenie a nabudúce sa pozerajte, čo vám dovoľujú limity v zadaní.

Ako teda vymyslieť prvé riešenie, ktoré spracováva každú otázku v čase \(O(n)\)? Potrebujeme spracovávať dve operácie – invertovanie intervalu a zistenie najdlhšej podpostupnosti núl a následne jednotiek. Prvá operácia je ľahká. Naozaj prejdeme celý zadaný interval a zmením každé číslo na to opačné.

Čo sa týka druhej, použijeme veľmi jednoduché dynamické programovanie. Budeme poľom prechádzať zľava doprava a v každom momente si budeme pamätať dve čísla. Aká je najdlhšia podpostupnosť z doposiaľ videných prvkov, ktorá končí nulou (\(p_0\)) a aká je najdlhšia postupnosť z doposiaľ videných prvkov končiaca jednotkou (\(p_1\)). Nie je problém vymyslieť, ako sa tieto čísla budú meniť.

Ak budeme mať na aktuálnom políčku nulu, tak \(p_0 = p_0+1\) a \(p_1\) zostane nezmenené. V opačnom prípade, keď sa na políčku nachádza jednotka, tak \(p_0\) zostane nezmenené a \(p_1 = \max(p_0+1, p_1+1)\). Po prejdení celého poľa si jednoducho vyberieme väčšiu z hodnôť \(p_0\) a \(p_1\) ako dĺžku najdlhšej hľadanej podpostupnosti.

Pamäťová zložitosť takéhoto riešenia je \(O(n)\) a časová \(O(nq)\). Aj samotný program, ktorý implementuje toto riešenie je pomerne jednoduchý:

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

int main() {
    int n;
    scanf("%d",&n);
    vector<int> A;
    For(i,n) {
        char c;
        scanf(" %c",&c);
        A.push_back(c-'0');
    }
    int q;
    scanf("%d",&q);
    For(i,q) {
        int t;
        scanf(" %d",&t);
        if(t==1) {
            int p0=0,p1=0;
            For(j,n) {
                if(A[j]==0) p0=p0+1;
                else p1=max(p0+1,p1+1);
            }
            printf("%d\n",max(p0,p1));
        }
        else {
            int z,k;
            scanf("%d %d",&z,&k);
            for(int j=z-1; j<k; j++) A[j]=(A[j]+1)%2;
        }
    }
}

Intervalový strom

Keď sa pozeráme na úlohu, mali by sme sa snažiť nájsť podobnosti s inými úlohami, ktoré sme riešili. Z veľkostí vstupu nám môže vyplynúť, že chceme každú operáciu vykonať v čase \(O(\log n)\). Naviac naše operácie sa zameriavajú na intervaly našeho poľa. Toto všetko by malo ukazovať na to, že chceme použiť intervalový strom.

Samozrejme, toto nemusí byť zakaždým pravda. Môže sa stať, že riešenie použije vyhľadávacie stromy, alebo otázky spracováva offline, alebo kopec iných možností. Vždy sa však oplatí si prejsť zoznam používaných konceptov a skúsiť ich aplikovať.

Na prvý pohľad to však pôsobí zvláštne. Klasický sčítací, či maximový/minimový strom nám je v tomto prípade úplne nanič. To však nie je jediné využitie intervalových stromov. Tie nám totiž ponúkajú oveľa všeobecnejšiu štruktúru, ktorá si pamätá v každom vrchole nejaké informácie o prislúchajúcom intervale a vie jednoduchým spôsobom spájať informácie pre synov do informácií pre otca. V našej úlohe teda musíme vymyslieť, čo si musí pamätať každý z vrcholov.

Vieme, že jedna z otázok, ktorú sa pýtame, je: “Aká je dĺžka najdlhšej podpostupnosti, ktorá začína nulami a končí jednotkami, na celom poli?” Čo v podstate znamená, že túto hodnotu si musí pamätať koreň našeho intervalového stromu. A ak si to pamätá on, musí si to pamätať každý vrchol. Pre každý vrchol si teda zapamätáme hodnotu \(p_{01}\) – dĺžku najdlhšej podpostupnosti, ktorá sa nachádza na danom intervale, začína nulami a končí jednotkami.

Otázkou ale je, či vieme z hodnôt \(p_{01}\) pre synov určiť túto hodnotu aj pre otca. Odpoveďou je, že nie. Ak totiž spojím dve takéto postupnosti, dostanem postupnosť, ktorá začína nulami, končí jednotkami, ale niekde v strede sa to ešte zmení z jednotiek na nuly a opačne. A to nie je dobre – v celej podpostupnosti máme mať len jeden zlom medzi nulami a jednotkami.

Pozrime sa, kde sa tento zlom nachádza. Ak sa nachádza v interale prislúchajúcom ľavému synovi, znamená to, že z pravého syna môžeme zobrať už iba jednotky. A kľudne môžeme zobrať všetky jedotky, ktoré sa v jeho intervale nachádzajú. Naopak, ak sa zlom nachádza v pravom synovi, z ľavého môžeme zobrať všetky nuly. To znamená, že každý vrchol si musí pamätať ďalšie dve hodnoty – \(p_0\) je počet núl v jeho intervale a \(p_1\) je počet jednotiek.

V tomto okamihu vieme všetky tri hodnoty vyrátať veľmi jednoduchým spôsobom. Hodnoty \(l_0\), \(l_1\) a \(l_{01}\) nech patria ľavému synovi, hodnoty \(r_0\), \(r_1\) a \(r_{01}\) pravému a tie s \(p\) patria otcovi. Potom platí:

\[p_0 = l_0 + r_0\] \[p_1 = l_1 + r_1\] \[p_{01} = \max (l_{01}+r_1, l_0+r_{01}, l_0+r_1)\]

Všetky vyššie uvedené vzorce by mali byť intuitívne, ak vám niektorý nie je jasný, nakreslite si to. Posledná možnosť \(l_0+r_1\) nastane vtedy, ak je zlom presne medzi ľavým a pravým synom.

Tieto tri hodnoty nám stačia, keď sa nám invertuje iba interval o dĺžke jeden. Keďže však budeme meniť aj väčšie intervaly, pridáme si do každého vrcholu ešte hodnotu \(p_{10}\) – najdlhšia podpostupnosť v tomto intervale, ktorá začína jednotkami a končí nulami. Jej rátanie je veľmi podobné tomu pri \(p_{01}\):

\[p_{10} = \max (l_{10}+r_0, l_1 + r_{10}, l_1+r_0)\]

Spracovávanie dlších intervalov

V našom riešení už vieme odpovedať na jeden typ operácie (otázku), tým že jednoducho z koreňa vypíšeme hodnotu \(p_{01}\). Treba však vyriešiť, ako meniť náš strom na základe druhého typu operácií (inverz intervalu).

V prípade, že menený interval má dlžku \(1\), je všetko pomerne jednoduché. Proste zmeníme hodnotu tohto konkrétneho prvka v poli a následne postupujeme hore stromom až do koreňa, pričom zakaždým prepočítame hodnoty vo vrchole. Zložitosť takejto operácie je \(O(\log n)\). To nám však nepomôže, keď máme zmeniť dlhší interval.

V takomto prípade použijeme metódu, ktorá sa volá lazy loading. Namiesto toho, aby sme začali zdola, začneme od koreňa a postupne budeme zisťovať, ktoré vrcholy majú celý svoj interval vnútri invertovaného intervalu. Keď nájdeme takýto vrchol, spravíme nasledovné: vieme, že všetky čísla, ktoré ležia pod týmto vrcholom sa zmenili na opačné. Tým pádom sa nám vymenia hodnoty \(p_0\) a \(p_1\) a tiež \(p_{01}\) a \(p_{10}\) (preto sme si ju pridali). Tento vrchol \(x\) teda vieme opraviť na správne požadované hodnoty bez toho, aby sme mali správne hodnoty aj v jeho synoch.

Čo však s vrcholmi, ktoré ležia pod ním? Tým zatiaľ zatajíme, že sa zmenili, akurát si do tohto vrchola \(x\) v premennej \(lazy\) zaznačíme, že ešte nepovedal vrcholom pod sebou, že sa majú invertnúť. Následne prepočítame hodnoty všetkých vrcholov na ceste z koreňa do tohto vrchola a máme vybavené.

Čo však keď budeme potrebovať hodnotu z nejakého vrchola, ktorý má byť invertovaný, ale ešte o tom nevie? Ak sa stane niečo takéto, určite budeme musieť prejsť cez vrchol \(x\). Ten však v momente, keď cez neho prechádzame, zbadá, že ešte nepovedal vrcholom pod sebou, že sa majú invertovať, tak im to rýchlo oznámi a zmaže si hodnotu \(lazy\). Vrcholy pod ním si teda povymieňajú svoje hodnoty a zaznačia si hodnotu \(lazy\), lebo to musia povedať tým pod sebou. Tým pádom vždy, keď potrebujeme použiť hodnotu nejakého vrchola, tento vrchol už pozná svoje skutočné hodnoty a vie nám ich povedať.

Dôvod, prečo je niečo takéto rýchlejšie je ten, že robíme iba robotu, ktorá je absolútne nevyhnutná. Ak sa totiž nikdy nespýtame na žiaden vrchol pod \(x\), načo by sme im oznamovali, že sú zmenené? A vďaka premenným \(lazy\) si vieme pamätať, kto ešte musí niečo povedať. Tento princíp vôbec nie je taký zložitý, ako by sa mohlo na prvý pohľad zdať. Odporúčame si nakresliť nejaký strom na papier a popozerať sa, ako by sa tie hodnoty mali meniť a takisto si poriadne preštudovať nižšie uvedený program, hlavne funkcie \(update()\) a \(process\_lazy()\).

Zložitosť takejto operácie nie je o nič väčšia ako klasické intervalové vyhľadávanie – \(O(\log n)\). Dostávame algoritmus s časovou zložitosťou \(O(q \log n)\) a pamäťovou zložitosťou \(O(n)\).

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

struct vertex {
    int p0,p1,p01,p10;
    int lazy;
};

vertex T[3000047];
int moc2;

vertex create(int a, int b, int c, int d) {
    vertex v;
    v.p0=a; v.p1=b; v.p01=c; v.p10=d;
    v.lazy=0;
    return v;
}

void reverse_vertex(int v) {
    swap(T[v].p0,T[v].p1);
    swap(T[v].p01,T[v].p10);
}

void process_lazy(int v) {
    if(T[v].lazy%2==0) return;
    reverse_vertex(v);
    T[v].lazy=0;
    if(v>=moc2) return;
    T[2*v].lazy++; T[2*v+1].lazy++;
}

int answer() {
    process_lazy(1);
    return T[1].p01;
}

void repair(int v) {
    T[v].p0=T[2*v].p0+T[2*v+1].p0;
    T[v].p1=T[2*v].p1+T[2*v+1].p1;
    T[v].p01=max(T[2*v].p01+T[2*v+1].p1,max(T[2*v].p0+T[2*v+1].p01,T[2*v].p0+T[2*v+1].p1));
    T[v].p10=max(T[2*v].p10+T[2*v+1].p0,max(T[2*v].p1+T[2*v+1].p10,T[2*v].p1+T[2*v+1].p0));
}

//<from,to) je interval, ktory potrebujeme zmenit, <zac,kon) je interval, ktory patri vrcholu v
void update(int v, int from, int to, int zac, int kon) {
    process_lazy(v);
    if(to<=zac || kon<=from) return;
    if(from<=zac && to>=kon) {
        T[v].lazy++;
        process_lazy(v);
        return;
    }
    int stred=(zac+kon)/2;
    update(2*v,from,to,zac,stred);
    update(2*v+1,from,to,stred,kon);
    repair(v);
}

int main() {
    int n,m;
    scanf("%d",&n);
    moc2=1;
    while(n>moc2) moc2*=2;
    For(i,n) {
        char c;
        scanf(" %c",&c);
        if(c=='0') T[moc2+i]=create(1,0,1,1);
        else T[moc2+i]=create(0,1,1,1);
    }
    for(int i=moc2-1; i>0; i--) repair(i);
    scanf("%d",&m);
    int xx;
    For(i,m) {
        scanf(" %d",&xx);
        if(xx==1) printf("%d\n",answer());
        else {
            int l,r;
            scanf(" %d %d",&l,&r);
            l--;
            update(1,l,r,0,moc2);
        }
    }
return 0;
}