Zapytanie o minimalną wartość w zakresie
Otrzymasz listę liczb N i Q zapytań. Każde zapytanie jest określone przez dwie liczby i oraz j; odpowiedzią na każde zapytanie jest minimalna liczba z przedziału [i, j] (włącznie).
Uwaga: zakresy zapytań są określane przy użyciu indeksowania zaczynającego się od 0.
Wejście
Pierwsza linia zawiera N, ilość liczb całkowitych na naszej liście (N <= 100 000). Następna linia zawiera N liczb, które na pewno zmieszczą się w zmiennej typu int. Pod listą znajduje się liczba Q (Q <= 10 000). Każda z następnych Q linii zawiera dwie liczby i oraz j, które określają zakres zapytania, na które musisz odpowiedzieć (0 <= i, j <= N-1).
Wyjście:
Dla każdego zapytania wypisz odpowiedź na to zapytanie w osobnym wierszu w kolejności, w jakiej zostały wykonane zapytania.
Przykład:
Wejście:
3 1 4 1 2 1 1 1 2
Wyjście:
4 1
Zadanie jest tłumaczeniem zadania RMQSQ – Range Minimum Query. Źródło: https://www.spoj.com/problems/RMQSQ/
Autor zadania: https://www.spoj.com/users/joshkirstein/
Zadanie sprowadza się do wczytania ciągu liczb, a następnie wykonywania określonej liczy zapytań zwracającej zawierającej początek oraz koniec przedziału zwracając minimalną liczbę z tego przedziału. Można wykonać to zadanie metodą naiwną wczytując wszystkie liczby do tablicy, a następnie podczas wykonania każdego zapytania przechodzić pytany zakres sprawdzając każdą liczbę czy jest mniejsza od poprzednio znalezionej. Takie rozwiązanie ma liniową złożoność obliczeniową, jednak jest za wolne na potrzeby rozwiązania.
Kod źródłowy w C++ rozwiązania brute force:
#include <iostream> using namespace std; int tab[100001]; int main() { int n; cin >> n; for(int i = 0; i < n; ++i) { cin >> tab[i]; } int q; cin >> q; while(q--) { int a, b; cin >> a >> b; int minmum = tab[a]; for(a; a<=b; ++a) { minmum = min(tab[a], minmum); } cout<<minmum<<endl; } return 0; }
Może to zadanie rozwiązać inaczej, zwracając wartość najmniejszej liczy w przedziale z zapytania w czasie stałym. W tym celu należy wykonać przetwarzanie wstępne (preprocessing) generując tablice zawierające podciągi ciągu wejściowego. Tablic będzie tyle, ile maksymalnej potęgi dwójki zmieści się w długości ciągu N. Wygenerowane zostaną wszystkie możliwe podciągi dla każdej możliwej potęgi dwójki. Poniżej przedstawiono przykład podziału dla ciągu:
3 2 4 2 1 4 5 3
Pierwszy wiersz i oznacza numery indeksów w ciągu, a A jego wartości.
Podział wejściowego ciągu na podciągi o długości 20 – każdy podciąc o długości 20:
\[\genfrac{}{}{0pt}{}{i:}{A:}\ \ \ \underbrace{\ \genfrac{}{}{0pt}{}{0}{3}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{1}{2}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{2}{4}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{3}{2}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{4}{1}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{5}{4}}_{2^0},\underbrace{\genfrac{}{}{0pt}{}{6}{5}}_{2^0},\ \underbrace{\genfrac{}{}{0pt}{}{7}{3}}_{2^0}\ \ \ \]Kolejna podział na podciągi o długości 21 – zaczynając od pierwszego elementu ciągu, przesuwając się o jeden element w prawo:
\[\genfrac{}{}{0pt}{}{\mathrm{i:}}{\mathrm{A:}}\mathrm{\ \ \ }\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{0\ \ 1}}{\mathrm{3\ \ 2}}}_{{\mathrm{2}}^{\mathrm{1}}}\mathrm{,}\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{1\ }\mathrm{\ }\mathrm{2}}{\mathrm{2\ \ 4}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{1}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{2\ \ 3}}{\mathrm{4\ \ 2}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{1}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{3\ \ 4}}{\mathrm{2\ \ 1}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{1}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{4\ \ 5}}{\mathrm{1\ \ 4}}}_{{\mathrm{2}}^{\mathrm{1}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{5\ \ 6}}{\mathrm{4\ \ 5}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{1}}},\mathrm{\ }\underbrace{\mathrm{}\genfrac{}{}{0pt}{}{\mathrm{6\ \ 7}}{\mathrm{5\ \ 3}}}_{{\mathrm{2}}^{\mathrm{1}}}\mathrm{}\]Kolejny podział na podciągi o długości 22 – :
\[\genfrac{}{}{0pt}{}{\mathrm{i:}}{\mathrm{A:}}\mathrm{\ \ \ }\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{0\ \ 1\ \ 2\ \ 3\ }}{\mathrm{3\ \ 2\ \ 4\ \ 2\ }}}_{{\mathrm{2}}^{\mathrm{2}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{1\ \ 2\ \ 3\ \ 4}\mathrm{\ }}{\mathrm{2\ \ 4\ \ 2}\mathrm{\ \ 1}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{2}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{2\ \ 3\ \ 4\ \ 5}\mathrm{\ }}{\mathrm{4\ \ 2\ \ 1\ \ 4}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{2}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{3\ \ 4\ \ 5\ \ 6}\mathrm{\ }}{\mathrm{2\ \ 1\ \ 4\ \ 5}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{2}}},\underbrace{\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{4\ \ 5\ \ 6\ \ 7\ }}{\mathrm{1\ \ 4\ \ 5\ \ 3}\mathrm{\ }}}_{{\mathrm{2}}^{\mathrm{2}}}\]Kolejny podział na podciągi o długości 23 – jest to ostatnia potęga dwójki, która mieści się w N:
\[\genfrac{}{}{0pt}{}{i:}{A:}\ \ \ \underbrace{\ \genfrac{}{}{0pt}{}{0\ \ 1\ \ 2\ \ 3\ \ 4\ \ 5\ \ 6\ \ 7\ }{3\ \ 2\ \ 4\ \ 2\ \ 1\ \ 4\ \ 5\ \ 2\ }}_{2^3}\]Kolejny podział na podciąg 24 nie jest możliwy, gdyż nie mieści się w N.
Następnie generujemy tablicę określającą jaka maksymalna długość zakresu będącą potęgą dwójki zaczynająca się w danym zakresie.
Po wykonaniu preprocessingu wykonujemy zapytania polegające na sprawdzaniu maksymalnego zakresu będącego potęgą dwójki, który mieści się pomiędzy danymi indeksami, a następnie wykonujemy dwa odczyty z przygotowanej wcześniej tablicy zawierającej minimalną wartość w przedziale o długości wcześniej obliczonej maksymalnej potęgi dwójki mieszczącej się w przedziale. Pierwszy odczyt zaczyna się od i (początek przedziału zapytania) do i + maksymalna potęga dwójki mieszcząca się w pytanym zakresie. Drugi zaczyna się od j – maksymalna potęga dwójki mieszcząca się w pytanym zakresie, a kończy na j. Następnie wyciągamy minimum z odczytanych wartości. Przykład zapytania dla zakresu:
2 6
\[ \genfrac{}{}{0pt}{}{\mathrm{i:}}{\mathrm{A:}}\mathrm{\ \ }\genfrac{}{}{0pt}{}{0\mathrm{\ \ }\mathrm{1}}{\mathrm{3\ \ 2}}\mathrm{\ }\underbrace{\genfrac{}{}{0pt}{}{\mathrm{2\ \ 3\ \ 4\ \ 5}}{\mathrm{4\ \ 2\ \ 1\ \ 4}}}_{ \begin{array}{c} \mathrm{\ left}\mathrm{\ }\mathrm{+} \\ \mathrm{len\ }{\mathrm{(}\mathrm{2}}^{\mathrm{2}}\mathrm{)} \end{array} }\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{6\ \ 7}}{\mathrm{5\ \ 3}} \]
\[ \genfrac{}{}{0pt}{}{\mathrm{i:}}{\mathrm{A:}}\mathrm{\ \ \ }\genfrac{}{}{0pt}{}{\mathrm{0\ \ 1\ \ 2}}{\mathrm{3\ \ 2\ \ 4}}\mathrm{\ }\underbrace{\genfrac{}{}{0pt}{}{\mathrm{3\ \ 4\ \ 5\ \ 6}}{\mathrm{2\ \ 1\ \ 4\ \ 5}}}_{ \begin{array}{c} \mathrm{right}\mathrm{\ }\mathrm{-} \\ \mathrm{len\ }{\mathrm{(}\mathrm{2}}^{\mathrm{2}}\mathrm{)} \end{array} }\mathrm{\ }\genfrac{}{}{0pt}{}{\mathrm{7}}{\mathrm{3}} \]
W przykładzie o długości N = 8 dla zapytania z przedziału i = 2, j = 6 maksymalną potęga dwójki mieszczącą się w przedziałe [ i, j ] to 22. Wykonujemy zapytanie od indeksu 2 do 5 oraz od indeksu 3 do 6, a następnie zwracamy mniejszą z tych wartości. W ten sposób zapytanie można wykonać w czasie stałym bez liniowego przechodzenia zakresu zapytania.
Kod źródłowy zawierający użycie tablicy rzadkiej (sparse table):
#include <iostream> using namespace std; int n; int A[100000]; int Tmin[100000][17]; int log_array[100001]; void generate_tmin_array() { for(int i = 0; i < n; ++i) { Tmin[i][0] = A[i]; } for(int i = 1; (1 << i) <= n; ++i) { for(int j = 0; j <= n - (1 << i); ++j) { Tmin[j][i] = min(Tmin[j][i - 1], Tmin[j + (1 << (i - 1))][i - 1]); //cerr << "T[" << j << "][" << i << "]=" << Tmin[j][i] << endl; } } } void generate_log_array() { log_array[1] = 0; for(int i = 2; i <= n; ++i) { log_array[i] = log_array[i / 2] + 1; //cerr << "log[" << i << "]=" << log_array[i] << endl; } } int query(int left, int right) { int k = log_array[right - left + 1]; return min(Tmin[left][k], Tmin[right - (1 << k) + 1][k]); } int main() { cin >> n; for(int i = 0; i < n; ++i) { cin >> A[i]; } generate_tmin_array(); generate_log_array(); int q, l, r; cin >> q; while(q--) { cin >> l >> r; cout << query(l,r) << endl; } return 0; }
Więcej informacji o technice tablic rzadkich można znelźć pod hasłem: sparse table.