Jak określić, ile elementów z zakresu mieści się w innym podanym zakresie?

Question

Potrzebuję trochę pomocy próbuje dowiedzieć się czegoś:

Biorąc pod uwagę sekwencję nieuporządkowanych liczb (mniej niż 15.000) - A - Muszę odpowiedzieć Q odpytuje (Q < = 100000) formy I, J, X, Y które przekładają się jak następuje:

Ile liczb w zakresie [i, j] z a są większe (albo równa) niż x, ale mniejszy niż Y ze wszystkimi liczby w t Sekwencja jest mniejsza niż 5000.

Mam wrażenie, że wymaga to czegoś takiego jak O (logN) ze względu na dużą długość sekwencji i to sprawiło, że pomyślałem o BIT (binarnie indeksowane drzewa - z powodu zapytań), ale 2D BIT jest zbyt duży i wymaga dużo czasu, aby uruchomić go nawet po aktualizacji. Tak więc jedynym rozwiązaniem, które tu widzę, powinno być 1D BIT lub Segment Trees, ale nie mogę wymyślić, jak opracować rozwiązanie oparte na tych strukturach danych. Próbowałem zachować pozycje w uporządkowanym zbiorze liczb, ale nie mogę wymyślić, jak utworzyć BIT, która odpowiada na zapytania danego formularza.

Również algorytm powinien pasować do podobnych wartości 500ms dla podanych limitów. Edit 1: 500ms dla wszystkich operacji na wyprzedzającym i odpowiadając na pytania

EDIT 2: gdzie i, j są pozycje pierwszego i ostatniego elementu w sekwencji A szukać elementów większych niż X i mniejsze niż y

Edycja 3: przykład: Niech się 1, 3, 2, 4, 6, 3 i dalszych 1, 4, 3, 5, aby pomiędzy pozycjami 1 i 4 (włącznie) są 2 elementy (3 i 4) większe (lub równe) niż 3 i mniejsze niż 5

Z góry dziękuję! P.S: Przepraszamy za biedny angielski!

Answer 1

Wdrażaj zliczanie w zakresie 2D, tworząc uporządkowaną według BIT tablicę uporządkowanych podrysów. Na przykład, na wejściu

[1, 3, 2, 4, 6, 3] 

wyrocznią będzie

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

Wykorzystanie miejsca O (N log N) (oby porządku). Konstrukcja zajmuje czas O (N log N), jeśli jesteś ostrożny, lub czas O (N log^2 N), jeśli nie (nie ma powodu, aby być dla aplikacji metinks).

Aby odpowiedzieć na zapytanie z maksimum na indeksie sekwencji i wartości (cztery z nich można wykorzystać do odpowiedzi na zapytania wejściowe), wykonaj procedurę odczytu BIT dla indeksu maksymalnego, używając wyszukiwania binarnego w tablicy, aby zliczyć liczbę elementy nieprzekraczające wartości maksymalnej. Czas zapytania to O (log^2 N).