Mamy dany ciąg liczb  Rozważamy jego wszystkie spójne podciągi, czyli fragmenty postaci  które sortujemy w dość dziwny sposób. Mianowicie, aby porównać dwa fragmenty  i   szukamy najmniejszej liczby   która występuje różną liczbę razy w   i   Fragment   jest mniejszy niż  (co zapisujemy jako ) dokładnie wtedy, gdy owa liczba   występuje więcej razy w   niż w   Jeśli takiej liczby nie ma, to fragmenty są dla nas takie same; innymi słowy porównujemy multizbiory liczb występujące w obu fragmentach. Naszym zadaniem jest wyznaczenie multizbioru, który jest generowany przez -ty fragment w tym dziwnym porządku.

Pewnie warto przez chwilę zwątpić, czy ten porządek jest faktycznie porządkiem, czyli czy  implikuje, że  W przeciwnym przypadku ciężko byłoby bowiem mówić o sortowaniu. Na szczęście, okazuje się, że tak jest w istocie (  jest w rzeczywistości porządkiem leksykograficznym na fragmentach potraktowanych jako multizbiory). Ograniczenia podane w treści to  i   czyli wygenerowanie i posortowanie wszystkich fragmentów nie jest najlepszym z możliwych pomysłów. Ba,  problematyczne byłoby już nawet samo wygenerowanie fragmentów, nie mówiąc o tym, że porównanie dwóch fragmentów wydaje się wymagać czasu proporcjonalnego do ich długości. Zaczyna się robić ciekawie!

Co prawda, interesuje nas wyznaczenie -tego fragmentu, ale może wypadałoby urealnić oczekiwania i zacząć od próby skonstruowania efektywnego sposobu zliczania fragmentów, które są ściśle mniejsze od danego? Jest to dość standardowe podejście: zamiast rozwiązywać problem „znajdź najmniejsze dobre rozwiązanie”, zajmujemy się problemem„sprawdź, czy dane rozwiązanie jest dobre”. Potem zwykle wystarczy tylko zastosować wyszukiwanie binarne, choć w naszym przypadku sytuacja okaże się odrobinę bardziej skomplikowana.

Mając dany fragment   chcemy zliczyć fragmenty  dla których  Dość naturalne jest ustalenie   i przyjrzenie się wszystkim   które spełniają żądany warunek. Po chwili namysłu można dostrzec, że dodając kolejne elementy, możemy tylko zmniejszyć   które ma więcej wystąpień, zatem  Wynika stąd, że  spełniające warunek tworzą spójny przedział  Ale jak wyznaczyć to   Pewnie moglibyśmy zacząć od  i zwiększać je o jeden, dopóki  Brzmi to całkiem rozsądnie, choć pojawiają się co najmniej dwa problemy. Przede wszystkim potrzebujemy efektywnej metody na sprawdzanie, czy aktualne   należy zwiększyć o jeden. Jest to jednak dość łatwe: trzeba tylko skonstruować strukturę danych, która umożliwi nam przechowywanie dla każdego   różnicy między liczbą jego wystąpień w   i liczbą jego wystąpień w aktualnym fragmencie  oraz znajdowanie najmniejszego   dla którego ta różnica nie jest zerem. Musi również umożliwiać dodawanie nowych elementów  (co wiąże się ze zmniejszaniem odpowiadających im różnic). Taką strukturą może być zwykłe drzewo licznikowe, które umożliwia wykonywanie zarówno aktualizacji, jak i pytań w czasie  Dysponując takim narzędziem, będziemy w stanie wyznaczyć każde   w czasie  Niby fajnie, ale w tym momencie pojawia się drugi problem: przecież mamy aż  różnych   które wypadałoby znaleźć! Na szczęście można zauważyć, że  czyli dla kolejnego   możemy zacząć od  Jest to o tyle wygodne, że wspomniane przed chwilą drzewo licznikowe bez większych problemów pozwala także na zwiększenie   o jeden (czyli na usunięcie   z aktualnego fragmentu). Zatem dla kolejnych   zwiększamy   o jeden tak długo, jak aktualny fragment jest nie mniejszy niż   a następnie usuwamy   ze struktury. Ponieważ  wykonamy nie więcej niż  operacji na drzewie licznikowym, co daje sumaryczny czas  Fantastycznie.

Umiemy więc obliczyć, ile fragmentów jest mniejszych od danego   Używając bardzo podobnej metody, można też zliczyć fragmenty, które są równe   O ile więc tylko ktoś podrzuciłby nam fragment   umielibyśmy sprawdzić, czy faktycznie jest on -tym w naszym porządku (jeśli mamy  fragmentów, które są mniejsze od   i   takich, które są równe   wystarczy sprawdzić czy ). Niestety, nie mamy co liczyć na żadną życzliwą podpowiedź.

Spróbujemy zastosować strategię przypominającą wyszukiwanie binarne. Na dobry początek możemy stwierdzić, że szukany fragment na pewno znajduje się (w zdefiniowanym wyżej porządku) między  a (dowolnym) pustym fragmentem. Załóżmy więc, że wiemy już, iż szukany   leży między fragmentami  a   Co dalej? Przydałby nam się fragment   który leży mniej więcej w połowie drogi między  a   Mając   moglibyśmy szybko zliczyć fragmenty, które są od niego mniejsze, porównać tę liczbę z   i w zależności od wyniku zastąpić  lub   przez  (lub stwierdzić, że właśnie   jest szukanym fragmentem). Dobranie się do takiego   wydaje się jednak dość problematyczne, gdyż zakłada, że znamy cały porządek na fragmentach, a przecież tak nie jest.

Wyobraźmy sobie zbiór wszystkich fragmentów, które leżą (w naszym dziwnym porządku) między  a   Dla każdego   prawe końce takich  tworzą spójny przedział  co więcej, używając opisanej wyżej metody, możemy efektywnie wyznaczyć wszystkie  i  (po prostu rozważamy wszystkie fragmenty mniejsze niż   i odrzucamy te, które są również mniejsze niż  ). Można więc przedstawić interesujący nas zbiór jako sumę  mniejszych zbiorów (każdy z nich jest tak naprawdę posortowany, choć nie będzie to dla nas istotne). Ale co z tego?

Skoro nie wiemy, co zrobić, może warto wpaść w panikę i zrobić coś losowego. Spróbujmy więc wybrać losowy spośród fragmentów, które leżą między  a   Wystarczy tylko wylosować jeden ze zbiorów (jako że ich rozmiary mogą być dość różne, to wybieramy  z prawdopodobieństwem ), a następnie element w zbiorze. Wylosowawszy fragment   możemy sprawdzić, czy szukany fragment jest mniejszy czy większy (a może równy) od   A dlaczego to działa?

Wybierając losowy element, mamy sporą szansę, że liczba elementów między  a   istotnie się zmniejszy. Najłatwiej wyobrazić sobie sytuację, korzystając z poniższej ilustracji, na której kolejne kropki reprezentują elementy między  a   ułożone w kolejności zgodnej z naszym dziwnym porządkiem. Powiedzmy, że jest ich   a szukany element to kolorowa kropka na pozycji   Skoro wybieramy losowy element, to z prawdopodobieństwem   będzie on w środkowym okienku długości   Tak naprawdę sprawdzamy, czy wybrany element jest na prawo czy na lewo od szukanego, i w zależności od wyniku porównania pozbywamy się elementów na lewo lub na prawo od tego losowo wybranego. A to jest bardzo wygodne: zawsze pozbędziemy się przynajmniej lewego lub prawego kawałka długości   Czyli mamy przynajmniej  szansy na to, że liczba elementów między  a   spadnie przynajmniej o jedną czwartą.

Skoro zaczynamy z   kandydatami, szansa na to, że konieczne okaże się dużo więcej niż, powiedzmy,  iteracji, wydaje się niewielka. Darujemy sobie szczegółowe rachunki, wymagają one bowiem pewnej elementarnej wiedzy z rachunku prawdopodobieństwa: uwierzcie mi, że oczekiwana liczba rund to   Otrzymaliśmy więc rozwiązanie o oczekiwanym czasie działania  które w dodatku nie jest bardzo skomplikowane implementacyjnie.