Zadanie
Udalosti spomínané v tomto zadaní sú založené na pravdivých faktoch. Však si vyžiadaj vystúpenie, keď ho najbližšie stretneš.
Komu z nás sa nepáči mágia? Rýchle prsty, odvádzanie pozornosti a na prvý pohľad neuskutočniteľné veci? Niet divu, že aj Mišof sa v svojej mladosti naučil zopár trikov, ktoré teraz predvádza na skrátenie dlhej chvíle alebo na machrovanie v krčme.
Pozná pár kartových trikov, necháva miznúť zápalky a rôzne iné predmety, na povrazoch sa objavujú všelijaké uzly a dokonca dokáže opraviť roztrhnutú bankovku. Ako to robí? To ti, samozrejme, nemôžem povedať. Chápeš, tajomstvo kúzelníka.
Nedávno sa Mišof naučil nový trik a preto ti ho chcel predviesť. Do radu postavil \(n\) nepriehľadných pohárov otočených hore dnom. Pod niektoré z nich položil guličku. Spýtal sa ťa na súvislý interval pohárov a začal odkrývať, čo sa nachádza pod nimi. Na tvoje prekvapenie pod každým z vybraných pohárov bolo presne to, čo si neočakával. Ak tam na začiatku gulička bola, teraz tam nie je a naopak. Uau. Potom guličky opäť zakryl a postup opakoval s novým intervalom. Si okúzlený?1
“A to nie je všetko!” chváli sa Mišof. “Tiež ti viem ukázať najdlhšiu, nie nutne súvislú podpostupnosť pohárov, v ktorej sa pod pohármi najskôr guličky nenachádzajú a potom sa tam už stále nachádzajú.”
“Ale však to nie je ťažké.” Povieš a po chvíli premýšľania ukážeš správnu podpostupnosť.
“Áno? A dokážeš to, aj keď ti zmením tento interval, aj tento a nakoniec aj tento?” nedá pokoj Mišof.
No čo, dokážeš?
Úloha
Na vstupe dostaneš popis postupnosti a zmeny, ktoré nastali. Každá zmena je daná (uzavretým) intervalom pohárov. V tomto intervale sa objaví gulička pod každým pohárom, kde sa nenachádzala a zmizne spod každého pohára, kde bola. Jednotlivé zmeny na seba postupne naväzujú.
Raz za čas sa ťa Mišof opýta otázku: Aká je dĺžka najdlhšej (nesúvislej) podpostupnosti, kde na začiatku tejto podpostupnosti sú prázdne poháre a na konci poháre s guličkou? Presnejšie, po žiadnom pohári, pod ktorým je skrytá gulička nemôže v tejto podpostupnosti nasledovať pohár, pod ktorým gulička nie je.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 300\,000\)) – počet pohárov v postupnosti.
V druhom riadku je reťazec znakov 0
a 1
, kde 0
reprezentuje pohár, pod ktorým sa gulička nenachádza, a 1
reprezentuje pohár so skrytou guličkou. Tento reťazec určuje začiatočné rozmiestnenie guličiek.
V treťom riadku je číslo \(q\) (\(1 \leq q \leq 300\,000\)) – počet udalostí.
Nasleduje \(q\) riadkov popisujúcich jednotlivé udalosti. Ak sa v riadku nachádza iba jediný znak 1
, znamená to, že Mišof sa pýta otázku na aktuálny stav pohárov a guličiek. Ak riadok začína znakom 2
, znamená to zmenu intervalu, ktorý je definovaný nasledujúcimi dvoma číslami \(x_i\) a \(y_i\) (\(1 \leq x_i,y_i \leq n\)) na riadku. Prvé číslo je začiatok a druhé číslo je koniec daného intervalu.
Úloha má osem testovacích sád. V prvých piatich z nich platí, že \(n\cdot q \leq 1\,000\,000\). Navyše, v každej párnej sade platí, že \(x_i=y_i\).
Formát výstupu
Pre každú Mišofovu otázku, udalosť 1
, vypíšte jedno číslo – dĺžku najdlhšej podpostupnosti pohárov, kde sa všetky poháre, pod ktorými nie je gulička, nachádzajú pred všetkými pohármi, pod ktorými gulička je.
Príklad
Input:
5
00001
6
1
2 1 2
1
2 1 1
2 4 4
1
Output:
5
3
4
V prvej otázke je správna odpoveď celá postupnosť. Po prvej zmene vyzerá celá postupnosť 11001
. V tomto prípade jedna so správnych podpostupností pozostáva iba z jednotiek. Na konci dostaneme 01011
a do výsledku vyberiem obe nuly a posledné dve jednotky.
Tak stále buď, ale ak by ťa zaujímalo ako sa také niečo dá spraviť, odporúčam pozrieť www.youtube.com/watch?v=8osRaFTtgHo↩
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;
}
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ť.