Zadanie polega na wypisaniu na jakiej pozycji jest jedynka, w ciągu wejściowym, a następnie wydajnie odwrócić liczby, i wypisać pozycję dwójki, znowu odwrócić i napisać pozycję trójki itd...
Trudnością zadania jest znalezienie sposobu na wydajne odwracanie. Gdyby to wprost symulować byłaby złożoność O(n^2) czyli za dużo.
Mam pomysł, ale nie wiem czy nie za wolny - byłby O(n^(3/2)). Pomysł polega na tym zrobić lazy odwracanie. Przechodzimy od lewej do prawej i zapisujemy sobie w jakieś liście przedziały do odwrócenia, dla każdej liczby przetwarzamy każdy przedział który nachodzi na tę liczbę i dodajemy nowy przedział do listy. Jeżeli w liście nazbiera się więcej niż n^(1/2) przedziałów to wykonujemy te odwracania. Pojedyncze odwrócenie zajmie O(n), a wykonamy ich co najwyżej n^(1/2) razy, więc zajmie to razem O(n^(3/2)). Natomiast samo przetwarzanie wykona się n razy i maksymalnie lista ma rozmiar n^(1/2) więc to też zajmie O(n^(3/2)). Mamy więc O(n^(3/2) + n^(3/2)) = O(n^(3/2))