Узумаки
Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Анализа решења: Младен Пузић
Тестирање: Алекса Милисављевић
Први подзадатак
У овом подзадатку можемо симулирати мешање клонова и на крају исписати моћ клона на позицији K.
За сваку операцију, подниз клонова можемо сортирати растуће било којим ефикасним алгоритмом сортирања (сложености N\log N).
Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)
Други подзадатак
Слично као претходни подзадатак, само за операцију другог типа подниз морамо сортирати у опадајућем поретку.
Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)
Трећи подзадатак
Потребно је приметити да је низ у Узумаки поретку ако и само ако је ,спирално сортиран’', односно, да је најмањи елемент на првој позицији, други најмањи на последњој позицији, трећи најмањи на другој позицији, четврти најмањи на претпоследњој позицији, итд.
Након тога, слично као претходни подзадатак, само за операцију трећег типа можемо подниз копирати у нови низ, сортирати растуће, и онда поређати назад у оригинални низ у Узумаки поретку.
Временска сложеност: O(QN\log N)
Меморијска сложеност: O(N)
Четврти подзадатак
Решење ће бити најмањи елемент који се налази у последњем интервалу који садржи први елемент (у тренутку те операције). Онда су у оптицају сви елементи који су на почетку низа у том интервалу, али и сви елементи који претходним операцијама заврше у том интервалу. Назовимо овај интервал x_1.
Идемо уназад по операцијама од овог интервала и нађимо први следећи који се сече са интервалом x_1 (назовимо га x_2). Сада знамо да решење може бити и било шта из уније x_1 \cup x_2, у тренутку операције (пошто ће најмањи елемент из x_2 завршити у интервалу x_1 након операције). Настављамо даље и у унију додајемо све интервале који се секу са досадашњом унијом.
На крају ћемо имати унију свих тих интервала, која ће представљати префикс низа - одакле је најмањи број решење задатка.
Временска сложеност: O(N + Q)
Меморијска сложеност: O(N + Q)
Алтернативно решење: можемо приметити да у било ком интервалу, само најмањи елемент на том интервалу има потенцијал да буде решење. Такође, пошто је t_i = 1, решење ће се увек померати на лево.
Због тога, довољно је да за сваки интервал ефикасно нађемо најмањи елемент, и поставимо га на прву позицију у том интервалу. На крају, решење ће се налазити на првој позицији у низу. За ово можемо користити сегментно стабло.
Временска сложеност: O(Q\log N + N)
Меморијска сложеност: O(N)
Пети подзадатак
Пошто је A_i мало, има смисла да размишљамо о сортирању бројањем (counting sort) - ако имамо cnt_i појављивања броја i у неком интервалу и желимо да га сортирамо растуће, на првих cnt_1 позиција интервала поставићемо 1, на следећих cnt_2 позиција 2, итд. За сортирање опадајуће бисмо само ишли обрнутим редоследом.
Дакле, потребно нам је да ефикасно бројимо све елементе на интервалу, и да их постављамо на узастопне позиције. Ово можемо урадити чувањем сегментног стабла са лењом пропагацијом за сваку могућу вредност. У сегментном стаблу за неку вредност, на позицијама где се налази та вредност потребно је да се налази 1, у супротном 0.
Налажење броја појављивања неког елемента се ради збиром на интервалу, док се постављање ради лењом пропагацијом - прво постављањем целог низа на нуле, па постављањем потребног интервала на јединице.
Временска сложеност: O(QA_i\log N + N)
Меморијска сложеност: O(A_iN)
Шести подзадатак
Прва два типа операција извршаваћемо на исти начин као у претходном подзадатку - потребно је додатно анализирати како ефикасно постављати елементе по Узумаки поретку.
Уколико је cnt_1 парно, прву половину јединица ћемо ставити на почетак, а другу половину на крај интервала. Уколико је непарно, јединицу вишка ставићемо на почетак.
Уколико је cnt_2 парно, опет ћемо прву половину двојки ставити на почетак преосталог низа, а остатак на крај. Уколико је непарно, овај пут је нешто компликованије. Уколико смо до сад (за све претходне вредности) ставили једнако елемената на почетак и крај низа, онда ће вишак елемент ићи на почетак. У супротном, вишак елемент иде на крај преосталог дела интервала.
Овакав процес настављамо док не попунимо низ.
Временска сложеност: O(QA_i\log N + N)
Меморијска сложеност: O(A_iN)
Седми подзадатак
У претходна два подзадатка смо успели да генеришемо цео низ на крају, док ћемо овде користити чињеницу да нам је потребно да нађемо само елемент на позицији K.
Уместо да тражимо конкретну вредност на тој позицији, покушајмо да проверимо да ли ће та вредност бити \geq x за произвољно x. Све елементе низа који су мањи од x заменимо нулама, а остале јединицама. Сада, уколико се на крају свих операција на позицији K нађе јединица, онда ће крајња вредност бити већа или једнака x. Ово можемо проверити применом претходног подзадатка са две вредности (а чак нам је довољно само једно сегментно стабло).
Сада када можемо ово ефикасно проверити, можемо користити бинарну претрагу по решењу како бисмо нашли праву вредност одговора.
Временска сложеност: O(Q\log N\log A_i + N)
Меморијска сложеност: O(N + Q)
Решење за 100 бодова
Комбинујемо решења претходна два подзадатка како бисмо омогућили сва три типа операција.
Временска сложеност: O(Q\log N\log A_i + N)
Меморијска сложеност: O(N + Q)
Алтернативно решење: уместо сегментог стабла можемо поделити низ на интервале нула и јединица и одржавати скуп тих интервала. Сваком операцијом се број интервала повећава за највише 3, док се може значајно смањити. Зато ће укупан број промена ових интервала бити O(N + Q).
Временска сложеност: O((N + Q)\log N\log A_i)
Меморијска сложеност: O(N + Q)
