Označme si najprv pre každého robotníka jeho periódu $P_i = a_i + b_i$.

Jednoduché riešenie

Jedno z priamočiarych riešení by mohlo vyzerať napríklad takto. Vytvoríme si pole W dĺžky $N$, kde hodnota W[i] bude počet robotníkov, ktorý pracujú v $i$-tej hodine. Keď nejaký robotník príde, tak zvýšime počet pracujúcich robotníkov pre každú z hodín, v ktorých bude pracovať. Naopak, ak odíde, tak znížime počet pracujúcich robotníkov v týchto hodinách.

Toto riešenie bude mať časovú zložitosť $O(N^2)$, lebo kvôli každému príchodu alebo odchodu môžeme zmeniť až $O(N)$ prvkov poľa W.

Ľahký robotníci

Poďme sa najprv zamerať na riešenie prvých dvoch sád. Hneď si môžeme všimnúť, že zásadný rozdiel medzi týmito sadami a ostatnými je, že $\max{P_i}$ je najviac $500$. Rozdeľme si teda všetkých robotníkov do skupín podľa ich periódy. Teraz pre každú z týchto skupín môžeme robiť to isté, čo pri predošlom riešení. Pre každú zo skupín už ale nepotrebujeme pole veľkosti až $N$. Pre skupinu s periódou $P$ nám stačí pole veľkosti $P$ (lebo počet pracujúcich robotníkov tejto skupiny v čase $t$ bude rovnaký, ako počet pracujúcich robotníkov v čase $t + P$).

Pre každú skupinu robotníkov si teda spravíme pole dĺžky $P$, kde na $i$-tom indexe bude počet robotníkov, ktorí pracujú v hodine $i$ modulo $P$. Pri príchode alebo odchode robotníka nám stačí prejsť celé toto pole a ku každému zvyšku, v ktorom by tento robotník pracoval, pripočítame (respektíve odčitame) $1$. Keď chceme zistiť, koľko robotníkov pracuje v čase $t$, tak sa stačí pre každú skupinu pozrieť na hodinu so správnym zvyškom ($t % P$) a tieto hodnoty sčítať.

Pridanie alebo odobratie jedného robotníka teda zaberie $O(\max{P_i})$ času a zisťovanie odpovede zaberie taktiež $O(\max{P_i})$ času. Toto riešenie má teda časovú zložitosť $O(N \max{P_i})$.

Ľahkí a ťažkí robotníci

Už vieme pomerne efektívne riešiť situáciu, v ktorej majú všetci robotníci malú periódu. Poďme teda využiť jeden z klasických trikov, ktorý sa dá v takejto situácií využiť: rozdelíme si robotníkov na “ľahkých” a “ťažkých” a každú z týchto skupín budeme riešiť separátne. Ľahký robotníci budú tý, ktorých perióda je menšia ako $\sqrt{N}$. Pre nich už úlohu vieme riešiť efektívne v čase $O(N \sqrt{N})$.

Ťažký robotníci

Čo ale spraviť s ťažkými robotníkmi? Môžeme využiť to, že počet periód, ktoré stihnú do konca šichty spraviť, bude malý. Presnejšie to bude najviac $\frac{N}{\sqrt{N}} = \sqrt{N}$ periód.

Pri každom príchode alebo odchode ťažkého robotníka teda potrebujeme zmeniť hodnoty $O(\sqrt{N})$ intervalov. Stačí už len vymyslieť, ako toto robiť efektívne. Mohli robiť pomocou intervalového stromu, ale dá sa to aj rýchlejšie pekným trikom s prefixovými súčtami.

Budeme si pamätať pole A dĺžky $N$. Keď chceme k intervalu $[a,b]$ pripočítať $1$, tak k A[a] pripočítame $1$ a od A[b+1] odčítame $1$. Týmto sme dosiahli to, že sme v poli prefixových súčtov poľa A na intervale $[a,b]$ pripočítali $1$. Ak chceme odčítavať, tak to bude fungovať rovnako, len treba zmenit znamienka.

Počet aktuálne pracujúcich ťažkých robotníkov teda môžeme počítať nasledovne. Keď príde alebo odíde nejaký ťažký robotník, tak si do poľa A na $O(\sqrt{N})$ pozícií poznačíme $\pm 1$. Tiež si postupne v pomocnej premennej budeme počítať prefixový súčet tohto poľa, čo bude vlastne hľadaný počet pracujúcich ťažkých robotníkov.

Odchody a príchody ťažkých robotníkov teda vieme riešiť v čase $O(\sqrt{N})$ a dopočítať, koľko ich pracuje v aktuálnom čase vieme v konštantnom čase.

Optimálne riešenie

Na vyriešenie celej úlohy nám už len stačí všetko skonbinovať dokopy. Na začiatku hodiny vyriešime príchod alebo odchod robotníka (podľa toho, či je ľahký alebo ťažký). Potom už len stačí zvlášť dopočíť počet pracujúcich ľahkých robotníkov a dopočítať aktuálny prefixový súčet pre ťažkých robotníkov, čím dostaneme finálnu odpoveď pre túto hodinu.

Celková časová zložitosť je $O(N \sqrt{N})$, lebo vyriešiť príchod a odchod robotníka vieme v čase $O(\sqrt{N})$ (bez ohľadu na to, čí je ľahký alebo ťažký) a dopočítať počet pracujúcich ľahkých robotníkov vieme tiež v čase $O(\sqrt{N})$. Počet pracujúcich ťažkých robotníkov počitame postupne pomocou prefixových súčtov v konštantom čase.

Pamäťová zložitosť je $O(N)$, lebo pre ťažkých robotníkov si pamätáme pole dĺžky $N$ a pre ľahkých robotníkov $\sqrt{N}$ polí dĺžky $O(\sqrt{N})$.

#include<bits/stdc++.h>
using namespace std;
#define a first
#define b second

void tazky_prichod(int cas, vector<int>& tazky, pair<int,int> robotnik){
    int perioda = robotnik.a + robotnik.b;

    // zmeny z pracovania na obdivovanie
    for(int i = cas + perioda;i < tazky.size();i += perioda)
        tazky[i] -= 1;

    // zmeny z obdivovania na pracovanie
    for(int i = cas + robotnik.a;i < tazky.size();i += perioda)
        tazky[i] += 1;
}

void tazky_odchod(int zaciatok, int cas, vector<int>& tazky, pair<int,int> robotnik){
    int perioda = robotnik.a + robotnik.b;

    // ak aktualne pracuje, tak ho treba hned odstranit
    if((cas - zaciatok)%perioda >= robotnik.a){
        tazky[cas] -= 1;
    }

    // zmeny z pracovania na obdivovanie
    for(int i = zaciatok + perioda;i < tazky.size();i += perioda)if(i > cas)
        tazky[i] += 1;

    // zmeny z obdivovania na pracovanie
    for(int i = zaciatok + robotnik.a;i < tazky.size();i += perioda)if(i > cas)
        tazky[i] -= 1;
}

void lahky_prichod(int cas, vector<vector<int>>& lahky, pair<int,int> robotnik){
    int perioda = robotnik.a + robotnik.b;

    // pripocitam 1 ku vsetkym zvyskom, v ktorych tento robotnik pracuje
    for(int i = robotnik.a;i < perioda;i++)
        lahky[perioda][(cas + i)%perioda] += 1;
}

void lahky_odchod(int zaciatok, vector<vector<int>>& lahky, pair<int,int> robotnik){
    int perioda = robotnik.a + robotnik.b;

    // odcitam 1 od vsetkych zvyskov, v ktorych tento robotnik pracoval
    for(int i = robotnik.a;i < perioda;i++)
        lahky[perioda][(zaciatok + i)%perioda] -= 1;
}

// pocet lahkych robotnikov pracujucich v danom case
int pocet_lahkych(int cas, vector<vector<int>>& lahky){
    int vysledok = 0;

    // staci sa pre kazdu periodu pozriet na spravny zvysok a vsetko scitat
    for(int period = 1;period < lahky.size();period++)
        vysledok += lahky[period][cas%period];

    return vysledok;
}

const int SQRT = 450;

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;

    vector<pair<int,int>> robotnici(n); // zoznam dvojic a_i, b_i
    vector<int> posledne_pridanie(n, -1); // cas, v ktorom dany robotnik posledne prisiel
    vector<vector<int>> lahky(SQRT, vector<int>(SQRT, 0));
    vector<int> tazky(m, 0);

    for(auto &robotnik : robotnici)
        cin >> robotnik.a >> robotnik.b;

    int prefix_sucet = 0; // pocet aktualne pracujucich tazkych robotnikov
    for(int cas = 0;cas < m;cas++){
        int op, index;
        cin >> op >> index;

        if(op == 1){
            if(robotnici[index].a + robotnici[index].b >= SQRT)
                tazky_prichod(cas, tazky, robotnici[index]);
            else
                lahky_prichod(cas, lahky, robotnici[index]);
            posledne_pridanie[index] = cas;
        }else{
            if(robotnici[index].a + robotnici[index].b >= SQRT)
                tazky_odchod(posledne_pridanie[index], cas, tazky, robotnici[index]);
            else
                lahky_odchod(posledne_pridanie[index], lahky, robotnici[index]);
        }

        prefix_sucet += tazky[cas];

        // vysledok je pocet pracujucich tazkych + lahkych robotnikov
        cout << prefix_sucet + pocet_lahkych(cas, lahky) << "\n";
    }
}