8. Antény vzorové riešenie

5 10
45 60 40 50 45
3
0 2
2 4
0 4

2
1
5

Vzorové riešenie tejto úlohy bude mať vtipnú časovú zložitosť \(O((n+q)\sqrt{n}\log f)\), kde \(n\) je počet antén, \(q\) je počet otázok a \(f\) je rozsah hodnôt pre frekvencie antén. Ako takáto veselá časová zložitosť vznikne? Uvidíme časom.

Jednoduchšia úloha

Zabudnime na to, že máme nejaké pole a nejaké otázky, a zamyslime sa nad jednoduchšou úlohou, ktorá vyzerá nasledovne: Dané je číslo \(\delta\). Začíname s prázdnou (multi)množinou. Následne dostaneme sadu príkazov, pričom každý je buď tvaru “pridaj toto číslo” alebo “odstráň toto skôr pridané číslo”. Všetky čísla sú celé z rozsahu od 0 po \(f\). Po každej operácii musíme odpovedať, koľko dvojíc čísel v našej množine má vzdialenosť aspoň \(\delta\).

Ako túto úlohu efektívne riešiť? Existujú mnohé dátové štruktúry, pomocou ktorých vieme každú otázku zodpovedať v logaritmickom čase. Napr. pomocou vhodného vyvažovaného binárneho stromu by sme pre danú postupnosť \(n\) príkazov vedeli každý príkaz spracovať v čase \(O(\log n)\), a to dokonca bez ohľadu na veľkosť \(f\).

Existujú však aj riešenia omnoho jednoduchšie na implementáciu. Asi najľahšie je použiť Fenwickov (“fínsky”) strom, resp. súčtový intervalový strom. Pre každé číslo od 0 po \(f\) si budeme v strome pamätať, koľkokrát sa už v našej množine nachádza. Strom nám následne umožní v čase \(O(\log f)\) o ľubovoľnom intervale zistiť, koľko prvkov našej množiny v ňom leží.

No a toto využijeme nasledovne: Ak napr. dostaneme príkaz pridať nový prvok \(x\), najskôr si zistíme, koľko prvkov leží v \((x-\delta,x+\delta)\) a z toho vieme vypočítať, koľko nových dvojíc dostatočne vzdialených prvkov nám práve pribudlo.

Toto riešenie teda každý príkaz (pridanie alebo odobratie čísla) spracuje v čase \(O(\log f)\).

Pôvodná úloha

Vráťme sa teraz k našej pôvodnej úlohe.

Technika, ktorú si ukážeme, sa dá použiť vždy, keď sú splnené isté predpoklady. V prvom rade potrebujeme, aby išlo (rovnako ako v tejto úlohe) o offline problém – teda všetky otázky dostaneme naraz a môžeme si vybrať, v akom poradí ich zodpovieme. To ale samo o sebe nestačí.

Druhá vlastnosť, ktorú potrebujeme, súvisí práve s vyššie uvedenou jednoduchšou úlohou. Naša technika bude použiteľná pre všetky problémy, kde takýmto spôsobom zjednodušenú úlohu vieme efektívne riešiť.

Odmocninové vedierka

Na vstupe sme dostali \(q\) rôznych otázok, ktoré máme všetky zodpovedať. Náš algoritmus bude efektívny vďaka tomu, že si otázky šikovne prerozdelíme do skupín a potom vyriešime vždy celú skupinu naraz.

Predstavme si, že sme si celý rad antén (pole dĺžky \(n\)) rozdelili na \(\sqrt{n}\) úsekov. Následne môžeme zobrať všetky otázky a roztriediť ich do \(\sqrt{n}\) vedierok podľa toho, v ktorom úseku začínajú.

Formálne, zoberme si \(s=\lceil\sqrt{n}\,\rceil\) a potom každú otázku \([l_i,h_i]\) umiestnime do vedierka \(\lfloor l_i/s\rfloor\).

Čo sme takto dostali? V každom vedierku máme otázky, ktoré začínajú zhruba na tom istom mieste. (Končiť však môžu veľmi rôzne. Vedierko číslo 0 môže obsahovať ako otázku na jediné políčko, tak aj otázku na úplne celé pole.)

Spracovanie jedného vedierka

Každé vedierko s otázkami teraz spracujeme nasledujúcim spôsobom:

1. Všetky otázky vo vedierku usporiadame vzostupne podľa ich konca.
2. Prvú otázku zodpovieme hrubou silou: začneme s prázdnou množinou a postupne po jednom do nej pridáme prvky úseku, na ktorý sa otázka pýta.
3. Každú ďalšiu otázku zodpovieme tak, že postupne prerobíme predchádzajúci interval na nový: najskôr pridávame prvky na konci, potom pridávame alebo uberáme prvky na začiatku.

Teda ak sme napr. práve zodpovedali otázku \([7, 47]\) a čaká nás otázka \([3, 52]\), tak postupne do našej množiny pridáme prvky na indexoch 48, 49, 50, 51, 52, 6, 5, 4, a 3. Ak by potom nasledovala otázka \([4, 53]\), tak by sme do našej množiny následne pridali prvok na indexe 53 a potom opäť odstránili prvok na indexe 3.

A to je už úplne všetko. Jednoduché, nie?

Odhad časovej zložitosti

Implemenácia je skutočne veľmi jednoduchá, odhad časovej zložitosti nás však trochu potrápi.

V každom vedierku, v ktorom máme aspoň jednu otázku, budeme jednu otázku spracúvať hrubou silou. Keďže táto otázka má dĺžku \(O(n)\), jej spracovanie si vyžiada \(O(n)\) množinových operácií. Ak by sme teda z každého z \(\sqrt n\) vedierok spracovali len prvú otázku, trvalo by to \(O(\sqrt{n}\cdot n\log f)\).

Koľko práce dokopy pridá spracovanie všetkých ostatných otázok?

V každom vedierku potrebujeme otázky usporiadať podľa konca. Ak každé vedierko samostatne usporiadame napríklad MergeSortom, dokopy nám to bude trvať \(O(q \log q)\) času (keďže dokopy je vo vedierkach \(q\) otázok). Iná možnosť s rovnakou časovou zložitosťou je usporiadať si na začiatku všetky otázky podľa konca a až potom ich prerozdeliť do vedierok – čím automaticky budú usporiadané v každom z vedierok. No keďže koniec je číslo z rozsahu 0 až \(n-1\), namiesto MergeSortu môžeme použiť CountSort, čím dostaneme zložitosť \(O(q + n)\). Ak je počet otázok \(q\) zhruba rovný počtu antén \(n\), časová zložitosť ľubovoľnej z týchto možností bude zanedbateľná oproti zvyšku riešenia.

Keď prerábame nejakú otázku na nasledujúcu, robíme dva typy zmien:

• pridávame prvky na pravom okraji otázky
• pridávame a uberáme prvky na ľavom okraji otázky

Pridávanie prvkov na pravom okraji je efektívne. Pozrime sa na ľubovoľné vedierko. Keďže sú otázky v ňom usporiadané podľa konca, vždy, keď ideme na nasledujúcu, budeme na pravom kraji len pridávať prvky, nikdy nie odoberať. A teda každý z \(n\) prvkov poľa takto pridáme do našej množiny nanajvýš raz. Dokopy teda tieto kroky pre jedno vedierko budú trvať \(O(n\log f)\). No a keďže vedierok je \(\sqrt{n}\), celkový čas strávený posúvaním pravého konca je \(O(n\sqrt{n}\log f)\).

No a aj pridávanie a uberanie prvkov na ľavom okraji je efektívne. Toto je to miesto, kde sa ukáže, prečo sme vlastne delili otázky do vedierok. Totiž keď sú dve otázky v tom istom vedierku, sú ich začiatky vzdialené nanajvýš o \(\sqrt n\). No a teda keď prerábame jednu z nich na druhú, na ľavom okraji stačí postupne spraviť \(O(\sqrt n)\) zmien. Dokopy pre všetkých \(q\) otázok teda dostávame \(O(q\sqrt n)\) zmien, a keďže každú vieme spraviť v čase \(O(\log f)\), celkový čas strávený týmito krokmi je \(O(q\sqrt n\log f)\).

Celkovú časovú zložitosť teraz dostaneme sčítaním vyššie uvedených odhadov.

Historická poznámka

Táto technika je pomerne známa v svete efektívnych algoritmov, ale do súťažného programovania dorazila až v roku 2009, kedy Mo Tao touto technikou vyriešil úlohu počas čínskeho prípravného sústredenia pred IOI. V súťažnom programovaní sa následne zaužívalo volať túto techniku Mo’s algorithm.

#include <bits/stdc++.h>
using namespace std;

struct Fenwick1D {
    int size;
    vector<int> T;
    Fenwick1D(int maxval) { size = 1; while (size < maxval) size <<= 1; T.clear(); T.resize(size+1,0); }
    void update(int x, int delta) { while (x <= size) { T[x] += delta; x += x & -x; } }
    int sum(int x1, int x2) { // sum in the closed interval [x1,x2]
        int res=0;
        --x1;
        while (x2) { res += T[x2]; x2 -= x2 & -x2; }
        while (x1) { res -= T[x1]; x1 -= x1 & -x1; }
        return res;
    }
};

const int SQRT = 317; // must be >=sqrt(maxN)

struct query { int lo, hi, id; };

void change(Fenwick1D &FT, int &curr_elements, long long &curr_pairs, int newval, int K, int delta) {
    int minv = max(1,newval-K+1), maxv = min(FT.size,newval+K-1);
    if (delta == -1) { FT.update(newval,delta); --curr_elements; }
    curr_pairs += delta * (curr_elements - FT.sum(minv,maxv));
    if (delta == +1) { FT.update(newval,delta); ++curr_elements; }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int N, delta;
    cin >> N >> delta;

    vector<int> F(N);
    for (int &f : F) cin >> f;
    
    int Q;
    vector< vector<query> > queries(SQRT);
    cin >> Q;
    for (int q=0; q<Q; ++q) {
        int l, h;
        cin >> l >> h;
        queries[l/SQRT].push_back( {l,h+1,q} );
    }

    vector<long long> answers(Q);

    for (int a=0; a<SQRT; ++a) {
        if (queries[a].empty()) continue;

        sort( queries[a].begin(), queries[a].end(), [](const query &A, const query &B) -> bool { return A.hi < B.hi; } );

        Fenwick1D FT(1000047);
        int curr_elements = 0;
        long long curr_pairs = 0;
        int curr_lo = queries[a][0].lo, curr_hi = queries[a][0].hi;
        for (int x=curr_lo; x<curr_hi; ++x) change( FT, curr_elements, curr_pairs, F[x], delta, +1 );
        answers[ queries[a][0].id ] = curr_pairs;
        for (unsigned b=1; b<queries[a].size(); ++b) {
            while (curr_hi < queries[a][b].hi) change( FT, curr_elements, curr_pairs, F[curr_hi++], delta, +1 );
            while (curr_lo > queries[a][b].lo) change( FT, curr_elements, curr_pairs, F[--curr_lo], delta, +1 );
            while (curr_lo < queries[a][b].lo) change( FT, curr_elements, curr_pairs, F[curr_lo++], delta, -1 );
            answers[ queries[a][b].id ] = curr_pairs;
        }
    }
    for (auto a : answers) cout << a << endl;
}