8. Opitý za volantom vzorové riešenie

4
5 7
3 4
1 2
0 6
8
5
7
6
7
3
3
3
2

2 0 3
1 3
1 0
0
2 1 3
2 2 3
1 3
1 3

V prvej časti vzoráku si ukážeme, ako sa postupným zlepšovaním vieme dopracovať k optimálnemu riešeniu pomocou checkpointov. Ku koncu si ukážeme pomalšie, ale pomerne rýchle riešenie pomocou intervalového stromu a pre fajnšmekrov aj optimálne riešenie, ktoré používa karteziánsky strom.

Výstraha: Odporúčame vám čítať vzorák od začiatku. Jednotlivé sekcie na seba niekedy netriviálne nadväzujú. Pri odhadoch časových zložitostí sa budú vyskytovať hlavne písmenká \(n =\) počet obmedzení, \(q =\) počet otázok a \(o =\) veľkosť výstupu. Ak nebude uvedené inak, pamäťová zložitosť je \(O(n)\).

Priamočiare \(O(n + qn + o)\)

Na začiatku načítame všetky dopravné obmedzenia a uložíme si ich v skoro ľubovoľnej dátovej štruktúre – pole, vektor, spájaný zoznam,… Čokoľvek, čo nám umožňuje prejsť všetkými prvkami.

Keď sa neskôr vodiči pýtajú na dopravné obmedzenia, ktoré sa ich týkajú, jednoducho pre každé dopravné obmedzenie zistíme, či sa vodič nachádza v jeho aktívnej zóne. Ak áno, obmedzenie si zapamätáme. Na konci všetky zapamätané dopravné obmedzenia vypíšeme v požadovanom formáte.

Pre každú otázku prechádzame zoznam všetkých obmedzení, čiže najpomalšia časť algoritmu si vyžaduje čas \(O(qn)\).

Neskúšajme obmedzenia začínajúce za pozíciou vodiča \(O(n + qn + o)\)

Všimnime si, že nemá zmysel skúšať dopravné obmedzenia, ktorých začiatok je na ceste neskôr ako pozícia vodiča. Môžeme tak vyskúšať nasledujúce vylepšenie:

Na začiatku si všetky obmedzenia utriedime podľa pozície ich začiatku. Na otázky potom vieme odpovedať efektívnejšie – ak je panikáriaci vodič na pozícii \(p\), postupne overujeme obmedzenia v poradí, ako sú utriedené. Keď narazíme na obmedzenie začínajúce na \(l > p\), vieme, že ďalej nemá zmysel skúšať.

Ak všetky obmedzenia pokrývajú len krátke úseky cesty a vodič spanikáril skoro na konci cesty, tento algoritmus začne pekne poporiadku testovať obmedzenia, ktoré začínajú na začiatku cesty. Väčšina obmedzení však vďaka ich zanedbateľnej dĺžke nebude aktívna. V najhoršom prípade tak stále môžeme potrebovať pre každú otázku prechádzať väčšinu obmedzení, hoci výstup môže byť pomerne malý.

Neskúšajme obmedzenia začínajúce za a končiace pred pozíciou vodiča \(O(n^2 + q + o)\)

Čo ak by si ale algoritmus pamätal len obmedzenia, ktoré boli aktívne iba malý kúsok pred vodičovou pozíciou \(p\)? Povedzme, že tie, čo boli aktívne na pozícii \(q \leq p\). Potom by algoritmus nemusel skúšať obmedzenia končiace pred pozíciou \(q\). Stačí mu vyskúšať len obmedzenia aktívne na \(q\) a obmedzenia začínajúce v intervale \((q, p\rangle\).

Keď predchádzajúcu myšlienku dotiahneme do totálneho extrému, dostaneme algoritmus, ktorý po načítaní dopravných obmedzení pre každú pozíciu vypočíta, ktoré obmedzenia sú na nej aktívne.

Ako to spravíme? Tak, ako to robia ľudia za volantom:

Na cestu si umiestnime značky dvoch typov – začiatok dopravného obmedzenia a jeho koniec. Pri každej značke si tiež pamätáme poradové číslo obmedzenia, ku ktorému sa vzťahuje. Dopravné značky si utriedime podľa ich pozícií. Následne simulujeme jazdu od začiatku cesty po jej koniec, pričom si udržujeme množinu aktívnych obmedzení. Keď sa posunieme o \(1\) pozíciu vpred, pozrieme sa na všetky dopravné značky na novej pozícii, a podľa nich upravíme množinu aktívnych obmedzení – pridáme alebo odstránime obmedzenie z množiny. Následne si pre danú pozíciu uložíme všetky aktívne obmedzenia.

Celkové množstvo toho, čo si algoritmus zapamätá, môže ale byť až \(O(n^2)\) – napríklad, keď máme \(n\) obmedzení, a \(i\)-te z nich je aktívne na intervale \(\langle i, i + n)\). Množinu aktívnych obmedzení si tak stačí pamätať v jednoduchom poli, kde pridanie a odobranie záznamu bude trvať \(O(n)\). Ak by sme nepotrebovali ukladať aktívne obmedzenia pre každú pozíciu, vieme množinu upravovať v čase \(O(\log{n})\), keď množinu implementujeme ako binárny vyhľadávací strom (std::set v C++). Túto optimalizáciu budeme používať v ďalších zlepšeniach algoritmu.

Keď už pre každú pozíciu vieme, ktoré obmedzenia sú na nej aktívne, každú otázku vieme spracovať v čase \(O(1 + \mbox{veľkosť výstupu})\). Pamäťová zložitosť je \(O(n^2)\).

Niečo prijateľnejšie \(O(n\sqrt{n} + q\sqrt{n}\log{n} + o\log{n})\)

Nebudeme si ukladať aktívne obmedzenia pre každú pozíciu, ale iba pre niektoré. Opäť simulujeme jazdu od začiatku cesty po jej koniec. Pozíciu, pre ktorú sa rozhodneme uložiť si aktívne obmedzenia, nazveme checkpoint. Ako prvý checkpoint zvolíme začiatok cesty. Keď sa potom posúvame vpred, štandardne si udržujeme množinu aktívnych obmedzení. Ak sme od posledného checkpointu videli aspoň \(\sqrt{n}\) značiek, uložíme si pre túto pozíciu aktívne obmedzenia a prehlásime ju za nový checkpoint. Pre každý checkpoint si pamätáme najviac \(n\) obmedzení a ľahko vidno, že checkpointov je rádovo \(\sqrt{n}\). Preto toto predspracovanie vieme spraviť v čase \(O(n\sqrt{n})\).

Ako odpovedáme na otázky? Keď je panikáriaci vodič na pozícii \(p\), nájdeme najbližší checkpoint, ktorý je pred alebo na pozícii \(p\). To vieme spraviť napríklad tak, že si pamätáme zoznam všetkých checkpointov utriedený podľa ich pozície, a binárne v ňom vyhľadáme v čase \(O(\log{\sqrt{n}}) = O(\log{n})\).

Všetky obmedzenia aktívne v checkpointe vložíme do množiny (v čase \(O(a\log{n})\), kde \(a\) je počet týchto obmedzení). Následne sa posúvame vpred, kým nie sme za pozíciou \(p\) a podľa značiek upravujeme množinu. Vieme, že značiek bude najviac \(\sqrt{n}\), takže toto spravíme v čase \(O(\sqrt{n}\log{n})\). Nakoniec ešte vypísanie časti výstupu trvá \(O(v)\).

Dokopy potrebujeme na jednu otázku čas \(O(\log{n} + a\log{n} + \sqrt{n}\log{n} + v)\). Podľa nasledujúceho pozorovania to prevedieme do krajšieho tvaru, v ktorom už nebude vystupovať \(a\).

Pozorovania o lokálnosti

Nech na pozícii \(p\) je aktívnych \(a\) obmedzení, a na úseku \((p, q\rangle\) je \(s\) značiek. Potom na pozícii \(q\) je aktívnych aspoň \(a - s\) a najviac \(a + s\) obmedzení.

Cestou od najbližšieho checkpointu k pozícii vodiča narazíme na najviac \(\sqrt{n}\) značiek, teda \(a - \sqrt{n} \leq v\), odkiaľ dostávame horný odhad pre \(a\): \(a \leq v + \sqrt{n}\). Dosadením dostaneme odhad času na jednu otázku \(O(\sqrt{n}\log{n} + v\log{n})\). Pamäťová zložitosť je \(O(n\sqrt{n})\).

#include <iostream>
#include <vector>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

void vloz_do_setu (vector<int>& src, set<int>& dest) {
    for (unsigned i=0; i<src.size(); i++) {
        dest.insert(src[i]);
    }
}

void zmaz_zo_setu (vector<int>& src, set<int>& dest) {
    for (unsigned i=0; i<src.size(); i++) {
        dest.erase(src[i]);
    }
}

void uloz_do_vektora (set<int>& src, vector<int>& dest) {
    for (set<int>::iterator it = src.begin(); it != src.end(); it++) {
        dest.push_back(*it);
    }
}

int n, len;
vector<vector<int> > zac;   // znacky zaciatku obmedzenia na pozicii
vector<vector<int> > kon;   // znacky konca obmedzenia na pozicii
vector<int> nextnonempty;   // najblizsia dalsia pozicia, na ktorej su znacky
vector<vector<int> > check;
vector<int> checkpoint_positions;

void spocitaj_nextnonempty(){
    nextnonempty.resize(len);
    nextnonempty[len-1] = len;
    for (int i=len-2; i>=0; i--) {
        if (zac[i+1].size() > 0 || kon[i+1].size() > 0)
            nextnonempty[i] = i+1;
        else
            nextnonempty[i] = nextnonempty[i+1];
    }
}
    
void spocitaj_checkpointy(){
    int sqn = ceil(sqrt(n));
    check.resize(len);
    
    set<int> aktivne;
    vloz_do_setu(zac[0], aktivne);
    zmaz_zo_setu(kon[0], aktivne);
    uloz_do_vektora(aktivne, check[0]);
    checkpoint_positions.push_back(0);
    
    int pocet_znaciek = 0;
    for (int i=1; i<len; i++) {
        vloz_do_setu(zac[i], aktivne);
        zmaz_zo_setu(kon[i], aktivne);
        pocet_znaciek += zac[i].size() + kon[i].size();
        if (pocet_znaciek >= sqn) {
            uloz_do_vektora(aktivne, check[i]);
            checkpoint_positions.push_back(i);
            pocet_znaciek = 0;
        }
    }
}

set<int> zisti_aktivne_obmedzenia(int vodic){
    if (vodic < 0 || vodic >= len)
        return set<int>();
    
    int pos = *(upper_bound(checkpoint_positions.begin(), checkpoint_positions.end(), vodic) - 1); 
    set<int> aktivne;
    vloz_do_setu(check[pos], aktivne);
    for (pos = nextnonempty[pos]; pos <= vodic; pos = nextnonempty[pos]) {
        vloz_do_setu(zac[pos], aktivne);
        zmaz_zo_setu(kon[pos], aktivne);
    }
    return aktivne;
}

int main () {
    cin >> n;
    len = 2*n + 1;
    zac.resize(len); kon.resize(len); 
    
    for (int i=0; i<n; i++) {
        int a, b;
        cin >> a >> b;
        if (b <= a) continue;
        zac[a].push_back(i);
        kon[b].push_back(i);
    }

    spocitaj_nextnonempty();
    spocitaj_checkpointy();

    int q;
    cin >> q;
    int maska = 0;
    for (int i=0; i<q; i++) {
        int vodic;
        cin >> vodic;
        vodic ^= maska;

        set<int> aktivne = zisti_aktivne_obmedzenia(vodic);

        cout << aktivne.size();
        for (set<int>::iterator it = aktivne.begin(); it != aktivne.end(); it++) {
            cout << " " << *it;
            maska ^= *it;
        }
        cout << "\n";
    }

    return 0;
}

Lepšie? Lepšie. \(O(n\sqrt{n} + q\sqrt{n} + o)\)

Zamyslime sa nad tým, prečo sme mali v predchádzajúcom riešení v časovej zložitosti tak veľa logaritmov. Pri každej otázke na pozíciu \(p\) sme museli zostrojiť množinu, a potom ju upravovať. Pritom nás ale vôbec nezaujíma obsah množiny na pozíciách iných ako \(p\). Ide to teda spraviť aj lepšie – zostrojíme si zoznam všetkých kandidátov – obmedzení, ktoré by mohli byť aktívne na \(p\). Tých je \(O(a + \sqrt{n})\). Pre každého kandidáta vieme v konštantom čase povedať, či je aktívny na pozícii \(p\).

Dostaneme tak oveľa prijateľnejší čas na jednu otázku \(O(\log{n} + a + \sqrt{n} + v) = O(\sqrt{n} + v)\).

Celé sa to dá v \(O(n + q + o)\)

Na prvý pohľad vyzerá táto časová zložitosť nedosiahnuteľne – veď na upravovanie množiny aktívnych obmedzení potrebujeme \(O(n\log{n})\) času a hľadanie najbližších checkpointov nám trvá \(O(q\log{n})\)! Ukážeme si teda najprv, ako tieto veci vieme robiť rýchlejšie.

Pri udržiavaní množiny, nás nezaujíma jej obsah na pozíciách, ktoré nie sú checkpoint. Predstavme si teda, že poznáme všetky aktívne obmedzenia pre checkpoint na pozícii \(p\), a nasledujúci checkpoint položíme na pozíciu \(q\). Ako vypočítame množinu aktívnych obmedzení pre \(q\)? Tak, ako sme v predchádzajúcom riešení odpovedali na otázky – vyskúšame všetky obmedzenia aktívne na \(p\), a všetky obmedzenia začínajúce v \((p, q\rangle\).

Časová zložitosť zostrojenia jedného checkpointu je teda \(O(a + b)\), kde \(a\) je počet obmedzení aktívnych v predchádzajúcom checkpointe a \(b\) je počet obmedzení začínajúcich v \((p, q\rangle\). Keď takto zostrojíme všetky checkpointy, dostaneme časovú zložitosť \(O(c + n)\), kde \(c\) je počet obmedzení zapamätaných v checkpointoch (súčet \(a\)-čok).

Nakoniec, hľadanie najbližšieho checkpointu vieme robiť rýchlejšie vďaka tomu, že všetky pozície sú od \(0\) po \(2n\). Pre každú pozíciu zistíme, ktorý checkpoint je najbližšie. Ak označme najbližší checkpoint pre pozíciu \(x\) ako P[x], ľahko vidno, že ak pozícia \(p\) je checkpoint, tak P[p] = p, inak P[p] = P[p-1]. Stačí nám teda raz vypočítať pole P v \(O(n)\).

A stačí na to táto jednoduchá úprava

Všetky prerekvizity už máme, a dostávame sa tak k jadru celého riešenia – k rozumnému umiestňovaniu checkpointov. Prvý checkpoint umiestnime štandardne na začiatok cesty. Ako umiestňujeme nasledujúce checkpointy? Označme \(a\) počet obmedzení v predchádzajúcom checkpointe. Vydáme sa z neho smerom dopredu, pričom si počítame počet značiek, ktoré sme cestou videli. Keď tento počet presiahne \(\frac{a}{2}\), našu pozíciu prehlásime za nasledujúci checkpoint.

A to je celé! Iba drobnou úpravou odmocninového riešenia dostaneme optimálne lineárne. Patrí sa ale dokázať, že je to naozaj lineárne.

Zamyslime sa nad tým, koľko si toho v checkpointoch pamätáme. V prvom checkpointe si pamätáme všetky obmedzenia začínajúce na pozícii \(0\), ktorých je najviac \(n\). Pre každý ďalší checkpoint máme z pozorovania o lokálnosti nasledujúci odhad:

Nech predchádzajúci checkpoint na pozícii \(p\) má \(a\) aktívnych obmedzení, a aktuálny checkpoint je na pozícii \(q\) a má \(b\) aktívnych obmedzení. Na intervale \((p, q\rangle\) je \(s \geq \frac{a}{2}\) značiek. Potom \(b \leq a + s \leq 3s\).

Teda počet zapamätaných obmedzení v aktuálnom checkpointe je rádovo najviac toľko, koľko značiek sme stretli cestou z predchádzajúceho checkpointu. Každá značka sa ale zrejme nachádza najviac v jednom úseku (pozícia checkpointu, pozícia nasledujúceho checkpointu>. Značiek je \(O(n)\), takže celkovo si vo všetkých checkpointoch pamätáme \(O(n)\) obmedzení a tak vieme spočítať všetky obmedzenia v checkpointoch v čase \(O(n)\).

Nakoniec sa zamyslíme, ako dlho nám trvá odpovedať na otázku. Nech je panikáriaci vodič na pozícii \(p\) a najbližší predošlý checkpoint je na \(q\). Označme \(a\) počet obmedzení v \(q\). Vieme, že na intervale \((q, p\rangle\) je \(s < \frac{a}{2}\) značiek. Podľa pozorovaní o lokálnosti vieme, že počet obmedzení v \(p\) je aspoň \(a - s > a - \frac{a}{2} = \frac{1}{2} a\). Ak teda označíme veľkosť výstupu pre túto otázku \(v\), platí \(v > \frac{1}{2} a\). Počet skúšaných kandidátov je \(a + s \leq \frac{3}{2} < 3v = O(v)\). Takže na každú otázku vieme odpovedať v čase \(O(1 + v)\).

Potrebujeme teda čas \(O(n)\) na predpočítanie a čas \(O(q + o)\) na odpovedanie – dokopy \(O(n + q + o)\).

#include <iostream>
#include <vector>
using namespace std;

struct Obmedzenie {
    int l, r, por;

    Obmedzenie(int l, int r, int por) : l(l), r(r), por(por) {}
    Obmedzenie(){}
    bool aktivne (int vodic) { return (vodic >= l && vodic < r); }
};

void pridaj_aktivne_obmedzenia(int vodic, vector<Obmedzenie>& kandidati, vector<Obmedzenie>& dest) {
    for (unsigned i=0; i<kandidati.size(); i++)
        if (kandidati[i].aktivne(vodic))
            dest.push_back(kandidati[i]);
}

int n, len;
vector<int> nextnonempty;
vector<int> znacky_na_pozicii, predosly_checkpoint;
vector<vector<Obmedzenie> > obmedzenia_od_pozicie, obmedzednia_v_checkpointe;

vector<Obmedzenie> obmedzenia_na_pozicii(int pozicia, int checkpoint){
    vector<Obmedzenie> obmedzenia;
    pridaj_aktivne_obmedzenia(pozicia, obmedzednia_v_checkpointe[checkpoint], obmedzenia);
    for (int j = nextnonempty[checkpoint]; j<=pozicia; j = nextnonempty[j]) {
        pridaj_aktivne_obmedzenia(pozicia, obmedzenia_od_pozicie[j], obmedzenia);
    }
    return obmedzenia;
}
    
void spocitaj_nextnonempty(){
    nextnonempty.resize(len);
    nextnonempty[len-1] = len;
    for (int i=len-2; i>=0; i--) {
        if (znacky_na_pozicii[i+1] > 0)
            nextnonempty[i] = i+1;
        else
            nextnonempty[i] = nextnonempty[i+1];
    }
}

void spocitaj_checkpointy(){
    obmedzednia_v_checkpointe.resize(len);
    predosly_checkpoint.resize(len);

    obmedzednia_v_checkpointe[0] = obmedzenia_od_pozicie[0];
    predosly_checkpoint[0] = 0;

    int pocet_znaciek = 0;
    for (int i=1; i<len; i++) {
        pocet_znaciek += znacky_na_pozicii[i];
        int predosly = predosly_checkpoint[i-1];
    
        if (pocet_znaciek >= (int)obmedzednia_v_checkpointe[predosly].size() / 2) {
            obmedzednia_v_checkpointe[i] = obmedzenia_na_pozicii(i, predosly);
            pocet_znaciek = 0;
            predosly_checkpoint[i] = i;
        }
        else {
            predosly_checkpoint[i] = predosly;
        }
    }
}

int main () {
    cin >> n;
    len = 2*n + 1;
    znacky_na_pozicii.resize(len, 0);
    obmedzenia_od_pozicie.resize(len);

    for (int i=0; i<n; i++) {
        int a, b;
        cin >> a >> b;
        if (b <= a) {
            continue;
        }
        obmedzenia_od_pozicie[a].push_back(Obmedzenie(a, b, i));
        znacky_na_pozicii[a]++;
        znacky_na_pozicii[b]++;
    }

    spocitaj_nextnonempty();
    spocitaj_checkpointy();

    int q;
    cin >> q;
    int maska = 0;
    for (int i=0; i<q; i++) {
        int vodic;
        cin >> vodic;
        vodic ^= maska;

        vector<Obmedzenie> ans(0);
        if (vodic >= 0 && vodic < len){
            ans = obmedzenia_na_pozicii(vodic, predosly_checkpoint[vodic]);
        }

        cout << ans.size();
        for (unsigned i=0; i<ans.size(); i++) {
            cout << " " << ans[i].por;
            maska ^= ans[i].por;
        }
        cout << "\n";
    }
    
    return 0;
}

Čestné uznania…

…získavajú nasledujúce riešenia. Prvé je založené na intervalovom strome, beží v čase \(O(n\log{n} + q\log{n} + o)\) a bolo obľúbené medzi riešiteľmi. Druhé je takisto optimálne, a založené na karteziánskom strome.

Riešenie intervalovým stromom

Na pozícii \(l\) si budeme pamätať všetky obmedzenia, ktoré začínajú na pozícii \(l\). Nad takýmto poľom zostrojíme nasledovný intervalový strom – v každom intervale si pamätáme všetky obmedzenia, ktoré majú začiatok v tomto intervale. Navyše si ich pamätáme usporiadané podľa pozície konca obmedzenia. Takýto intervalový strom vieme ľahko zostrojiť – ak už vieme, aké obmedzenia začínajú v intervale \(\langle l, s)\) a v akom poradí končia, a rovnakú informáciu máme aj pre interval \(\langle s,r)\), tak tieto dva intervaly vieme spojiť v lineárnom čase do intervalu \(\langle l,r)\). (Podobne, ako to robí merge sort.)

Keď chceme odpovedať vodičovi na pozícii \(p\), chceme vlastne nájsť všetky obmedzenia začínajúce v \(\langle 0, p+1)\), ktorých koncový bod je \(> p\). Rozložíme teda štandardne interval \(\langle 0, p+1)\) na \(O(\log{n})\) intervalov, ktoré zodpovedajú vrcholom v našom strome. Pre každý z týchto intervalov vieme, ktoré obmedzenia v ňom začínajú, a v akom poradí končia. Tak začneme tými, ktoré končia najneskôr, a postupne ich skúšame, kým nenájdeme prvé obmedzenie končiace na \(r \leq p\). Ďalej vieme, že nemá zmysel skúšať.

Časová zložitosť jednej odpovede je teda \(O(\log{n} + v)\) – potrebujeme \(O(\log{n})\) času na rozklad na jednotlivé intervaly, a v každom spravíme aspoň jednu operáciu. Čas na zostrojenie intervaláča je \(O(n\log{n})\) – dokopy máme čas \(O(n\log{n} + q\log{n} + o)\). Pamäťová zložitosť je \(O(n\log{n})\) – na každej úrovni intervalového stromu si totiž pamätáme všetky obmedzenia, a úrovní je \(O(\log{n})\).

Karteziánske riešenie

Veríme, že čitateľ si sám doplní znalosti o tom, čo to je karteziánsky strom, a ako sa zostrojuje. Najlepšie predtým, než sa pustí do čítania tohto riešenia.

Každé dopravné obmedzenie môžeme interpretovať ako bod v rovine – ak začína na pozícii \(l\) a končí na \(r\), tak mu bude zodpovedať bod so súradnicami \(l, r\). Predstavme si pre začiatok, že žiadne dve obmedzenia nezačínajú ani nekončia na tej istej pozícii. Nech je vodič na pozícii \(p\), a už máme zostrojený karteziánsky strom nad bodmi s \(x\)-súradnicou \(\leq p\). Ako nájdeme odpoveď?

Jednoducho – začneme v koreni karteziánskeho stromu, spracujeme ho, a prípadne sa posunieme do jeho ľavého a pravého syna. Čo to znamená “spracovať” a “posunúť” ? Vieme, že body v ľavom aj v pravom podstrome majú \(y\)-súradnicu menšiu ako spracovávaný vrchol. Takže ak aktuálne spracovávaný vrchol nevyhovuje (zodpovedá nejakému obmedzeniu \(l, r\) pre \(r \leq p\)), tak nemá zmysel pokračovať so synom. Ak vyhovuje, tak ho pridáme do zoznamu aktívnych obmedzení, a pokračujeme so synmi. Ľahko vidno, že takto spravíme rádovo \(O(1 + v)\) operácii.

Vidíme teda, že by sme chceli nejaký perzistentný karteziánsky strom. To vieme dosiahnuť nasledovne – štandardne pomocou zásobníku zostrojujeme karteziánsky strom nad poľom. Každý vrchol niekedy pridávame do stromu. Pozrime sa na tento moment – pridávaný vrchol je najpravejší vrchol stromu, takže môže mať iba ľavého otca. Toho si v danom vrchole zapamätáme.

Ako teraz odpovedáme panikáriacemu vodičovi na pozícii \(p\) ? Predpokladajme, že existuje obmedzenie začínajúce na \(p\), a označme jemu zodpovedajúci vrchol \(a_0\). Spracujeme jeho ľavý podstrom, a nájdeme ľavého otca \(a_0\). Nech to je \(a_1\), spracujeme ľavý podstrom \(a_1\), nájdeme ľavého otca \(a_1\), a opakujeme. A tak ďalej, až kým nenarazíme na niekoho, kto už ľavého otca nemá.

Ľahko vidno, že takto sme naozaj spracovali náš strom v takom stave, v akom bol po pridaní vrcholu \(p, p\). Konštrukcia stromu z poľa trvá \(O(n)\), a odpovedanie trvá dokopy \(O(q + o)\) – dokopy \(O(n + q + o)\). Ešte potrebujeme rozšíriť naše riešenie o technické detaily. Konkrétne, keď obmedzenia môžu začínať aj končiť na rovnakej pozícii, a keď nemusí pre každú pozíciu \(p\) existovať obmedzenie začínajúce na \(p\). Prenechávame čitateľovi.

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    vector<pair<int, int> > obm; // konce a id
    // na pozicii 0 je najpravejsi koniec, a dalej zostupne

    // pridame do zoznamu obmedzeni
    void push (pair<int, int> par) {
        obm.push_back(par);
    }
    // ziskame obmedzenia konciace po p
    void get (int p, vector<int>& ans) {
        for (unsigned i = 0; i < obm.size(); i++) {
            if (obm[i].first <= p) {
                break;
            }
            ans.push_back(obm[i].second);
        }
    }
    // vrati y suradnicu reprezentanta -- najvacsia y suradnica
    int y () {
        if (obm.empty()) {
            return -1;
        }
        return obm[0].first;
    }
};

struct CarTree {
    vector<Node> V; // pre kazdu poziciu si pamatame obmedzenia zacinajuce na nej
    vector<int> lsyn, rsyn, lotec; // lavy/pravy syn, lavy otec v strome

    CarTree (vector<pair<int, int> >& obm) {
        // obmedzenia podla ich konca
        vector<vector<pair<int, int> > > sorted;
        for (unsigned i = 0; i < obm.size(); i++) {
            int kon = obm[i].second;
            while ((int)sorted.size() <= kon) { // zvacsime sorted, aby bol koniec vnutri rozsahu
                sorted.push_back(vector<pair<int, int> >());
            }
            sorted[kon].push_back(make_pair(obm[i].first, i)); // zaciatok obmedzenia a jeho id
        }
        // pomocou sorted naplnime V
        for (int i = (int)sorted.size() - 1; i >= 0; i--) {
            for (unsigned j = 0; j < sorted[i].size(); j++) {
                // najprv dostatocne zvacsime V
                int zac = sorted[i][j].first;
                while ((int)V.size() <= zac) {
                    V.push_back(Node());
                }
                // vlozime
                int id = sorted[i][j].second;
                V[zac].push(make_pair(i, id));
            }
        }
        // pridame virtualne obmedzenia
        for (unsigned i = 0; i < V.size(); i++) {
            V[i].push(make_pair(i, -1));
        }
        // nakoniec zostrojime samotny strom -- lsyn, rsyn, lotec
        vector<pair<int, int> > S; // stack, pamatame si (max y sur, x sur)
        for (unsigned i = 0; i < V.size(); i++) {
            int last = -1; // posledny vybrany zo stacku
            while (!S.empty() && S.back().first < V[i].y()) {
                last = S.back().second;
                S.pop_back();
            }
            if (!S.empty()) {
                int j = S.back().second;
                rsyn[j] = i;
                lotec.push_back(j);
            }
            else {
                lotec.push_back(-1);
            }
            lsyn.push_back(last);
            rsyn.push_back(-1);
            S.push_back(make_pair(V[i].y(), i));
        }
    }
    // spracuje zadany vrchol
    void spracuj (int v, int p, vector<int>& ans) {
        if (v < 0 || v >= (int)V.size()) {
            return;
        }
        if (V[v].y() <= p) {
            return;
        }
        V[v].get(p, ans);
        spracuj(lsyn[v], p, ans);
        spracuj(rsyn[v], p, ans);
    }
    // odpovie na otazku
    void query (int p, vector<int>& ans) {
        int i = p;
        if (i >= (int)V.size()) {
            i = (int)V.size() - 1;
        }
        if (i < 0) {
            return;
        }
        while (i != -1) {
            V[i].get(p, ans);
            spracuj(lsyn[i], p, ans);
            i = lotec[i];
        }
    }
};

int main () {
    int n;
    cin >> n;
    vector<pair<int, int> > obm; // obmedzenia
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        obm.push_back(make_pair(a, b));
    }
    CarTree ct(obm);

    int q;
    cin >> q;
    int maska = 0;
    for (; q>0; q--) {
        int t;
        cin >> t;
        t ^= maska;
        vector<int> ans;
        ct.query(t, ans);
        cout << ans.size();
        for (unsigned i=0; i<ans.size(); i++) {
            cout << " " << ans[i];
            maska ^= ans[i];
        }
        cout << "\n";
    }

    return 0;
}