11833. Bajtocki Inspektorat Ochrony Środowiska 3 [BAJTIOS3]

Zadanie:
http://pl.spoj.com/problems/BAJTIOS3

Skrócony opis problemu:

Otrzymujemy $n \le 100000$ liczb. Każda z nich ($x_i$) ma przypisany indeks $i$. Następnie otrzymujemy $m \le 10000$ trójek liczb: $a$, $b$, $y$. Zadanie polega na znalezieniu dla każdego zapytania (j-tego) ilości takich $x_i$, że $i \in \left<a;b\right>$ oraz $x_i > y_j$.

Podejście naiwne:

Dla każdego zapytania sprawdzamy po prostu wszystkie $n$ liczb i zliczamy te spełniające wymagania.

Złożoność: $O(m \cdot n)$.

Podejście sprytne:

Możemy to zrobić drzewem przedziałowym drzew. Drzewo przedziałowe odpowiedzialne będzie za indeksy liczb, a drzewo dla każdej komórki w drzewie przedziałowym będzie odpowiedzialne za wartości liczb. Czyli będziemy dodawać najpierw te $n$ liczb do drzewa przedziałowego drzew w następujący sposób. Najpierw musimy wybrać indeksy drzew, które mamy zamiar uzupełnić. Robimy to w czasie logarytmicznym. Dla każdej komórki, która odpowiada za przedział w drzewie przedziałowym mamy jakieś drzewo zrównoważone. Do każdego drzewa w komórce którą odwiedzamy dodajemy (również w czasie logarytmicznym) wartość liczby.

Złożoność tej części wynosi $O\left(n \cdot \log^2{n}\right)$, bo dla każdej z $n$ liczb przechodzimy drzewo przedziałowe w czasie logarytmicznym, a może się pesymistycznie zdarzyć, że to będzie cały czas ten sam przedział, więc liczb w niektórych komórkach będzie n, więc dodawanie też zajmie logarytmiczny czas.

Następnie musimy jakoś obsłużyć zapytania. No więc dla przedziału z każdego zapytania $\left<a;b\right>$ sprawdzamy w czasie logarytmicznym komórki, które nas interesują, a w każdej z nich sprawdzamy w drzewie zrównoważonym ile jest liczb większych od $y_j$ z danego zapytania (również w czasie logarytmicznym).

Złożoność tej części to $O\left(m \cdot \log^2{n}\right)$.

Widzimy więc, że pierwszy poziom (drzewo przedziałowe) odpowiedzialny jest za warunek indeksów: $i \in \left<a;b\right>$, a drugi (drzewo zrównoważone) za warunek wartości: $x_i > y_j$. Końcowa złożoność to zatem $O\left((m+n) \cdot \log^2{n}\right)$.

Podejście sprytniejsze:

Możemy coś zauważyć i z poprzedniego drzewa drzew wyeliminować jeden poziom. Musielibyśmy zatem zamienić dwa warunki na jeden. Tym poziomem będzie drzewo wartości. Jeśli bowiem będziemy mieć w drzewie przedziałowym tylko wartości większe od danego $y_j$, to będziemy je wszystkie brali pod uwagę i można się będzie obyć bez sprawdzania drugiego warunku. No ale jak to zrobić? Możemy sobie posortować nasze $n$ liczb oraz osobno nasze zapytania - oba niemalejąco i z zapamiętaniem pierwotnej kolejności, w której zostały pobrane. No więc mamy sobie wszystko posortowane. I co nam to daje? No więc na początku tablicy mamy największe wartości. Możemy więc porównać wartości początkowe z tablic. Jeśli ta z tablicy $y$ będzie większa (lub równa), to znaczy, że w tablicy $x$ nie ma żadnej liczby spełniającej założenia, więc wpisujemy 0 do tablicy wynikowej o indeksie zapamiętanym dla danego zapytania (czyli tym pierwotnym miejscu, w którym się znajdował w zapytaniach, żeby również wypisać w odpowiedniej kolejności wyniki) i idziemy dalej w tablicy $y$ (w tablicy $x$ znajdujemy się nadal w tym samym miejscu). Teraz mamy już inne, mniejsze (lub równe) $y_j$. Okazuje się, że ono jest tym razem mniejsze od największego elementu w tablicy $x$. Dodajemy więc to $x_i$ do naszego drzewa przedziałowego, jako że będzie już rozpatrywane przez wszystkie pozostałe zapytania. Bo skoro zapytania są w porządku niemalejącym i dla danego zapytania $x_i > y_j$, to dla następnych tym bardziej skoro kolejne $y_{j+k}$ są mniejsze od $y_j$. A jak dodajemy to $x_i$? Tym razem nie zależy nam na wartości tego $x_i$, bo już nie będziemy musieli porównywać go z $y_j$. Wystarczy nam wiedzieć, że jest takie $x_i$ i w jakim miejscu się ono znajduje. Dodajemy więc 1 do komórek przedziałów w drzewie, w których to przedziałach zawiera się pierwotny indeks $x_i$ (który powinniśmy byli zapamiętać). No ale może się zdarzyć, że również $x_{i+1}>y_j$. Przechodzimy więc tablicę $x$ i dodajemy $x_i$ do drzewa przedziałowego aż nie napotkamy takiego $x_i$, który będzie mniejszy lub równy $y_j$. Jak już takie $x_i$ znajdziemy (albo skończą nam się $x_i$) to możemy przeszukać nasze drzewo przedziałowe zliczając ilość liczb, które już spełniają warunek $x_i>y_j$ i skupiając się tylko na właściwym przedziale (wykonując to w czasie logarytmicznym). Na końcu wypisujemy w odpowiedniej kolejności stablicowane wcześniej wyniki. Bo pomieszaliśmy zapytania, więc musimy zapamiętać ich kolejność i mając dla każdego wyniki odtworzyć poprawny ciąg odpowiedzi.

Złożoność końcowa to $O\left((n+m) \cdot \log{(n+m)}\right)$, bo najpierw sortujemy obie tablice ($O(n \cdot \log{n} + m \cdot \log{m})$), a potem przechodzimy tablice liniowo i dla każdej komórki $x$ i $y$ wykonujemy $O(\log{n})$ operacji.

Ostateczny algorytm (oparty na drzewie Fenwicka; można zrobić na zwykłym drzewie przedziałowym przy takiej samej złożoności asymptotycznej):

struct para
{
    int i;
    float x; 
    bool operator<(const para &a)const
    {
        return x > a.x;
    }
}tab2[100009]; // tablica przechowująca x_i
struct el:para{int a,b;}q[10009]; // tablica przechowująca zapytania - y_i
int tab[1<<17], ans[10009]; // tablica na drzewo Fenwicka oraz na wynik

int sum(int a) // zliczenie sumy komórek od 0 do a
{
    int s = 0;
    do s += tab[a];
    while(a -= a & -a);
    return s;
}
int sum(int a, int b) // zliczenie sumy komórek od a do b
{
    return sum(b) - (a ? sum(a-1) : 0);
}
void add(int a, int x, int n) // dodanie x do komórki a
{
    do tab[a] += x;
    while((a += a & -a) < n);
}

int main()
{
    int n, n2, m, i, j;

    scanf("%d", &n);
    n2 = n;
    if(n2-1 & n2) // rozszerzanie n do potęgi 2 jeśli nią nie jest
    {
        frexp(n2, &n2);
        n2 = 1 << n2;
    }
    for(i = 1; i <= n; ++i)
        scanf("%f", &tab2[i].x),
        tab2[i].i = i;
    scanf("%d", &m);
    for(i = 0; i < m; ++i)
        scanf("%d %d %f", &q[i].a, &q[i].b, &q[i].x),
        q[i].i = i;
    sort(tab2+1, tab2+n+1); sort(q, q+m);
    for(i = 0, j = 1; i < m; ++i) // dla każdego zapytania
    {
        while(j <= n && tab2[j].x > q[i].x) // dopóki istnieje x_j większe od y_i
            add(tab2[j--].i, 1, n2); // dodaj to x_j do drzewa Fenwicka
        ans[q[i].i] = sum(q[i].a, q[i].b); // sprawdź ile jest x w danym przedziale i zapisz to do tymczasowej tablicy
    }
    for(i = 0; i < m; ++i) // wypisywanie wyników w odpowiedniej kolejności
        printf("%d\n", ans[i]);
}