На почту пришло письмо следующего содержания:
Hello,
Next weeks we will arrange several high level contest in order to allow the ACM ICPC World Finals contestants to prepare as better as possible. The first of them will take place this Saturday (April 23th) at 9:00 UTC. A really hard contest, a present from the great Rujia Liu to all of us.
Next weeks we will arrange several high level contest in order to allow the ACM ICPC World Finals contestants to prepare as better as possible. The first of them will take place this Saturday (April 23th) at 9:00 UTC. A really hard contest, a present from the great Rujia Liu to all of us.
На сайте увы сказано, что это контест на структуры данных. Также сказано, что он будет длиться 24 часа с отдельным зачетом по первым 5 часам.
Хотелось бы узнать у тех, кто уже учавствовал в подобных контестах/контестах этого автора, будет ли это вполне адекватный сложный тренировочный АСМ-контест, который можно написать как командную тренировку или же это будет жутко тематический контест с рассчитанными на 24 часа гробами, вместо которого лучше написать какую-то другую тренировку?
Ссылка: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=66&page=show_problem&problem=3141
Пробовал решать деревом отрезков, в каждой вершине которого хранится сбалансированное дерево поиска (конкретно декартово). Собственно такая структура позволяет находить кол-во чисел на отрезке больших или меньших некоторого заданного за O(log^2(n)). Но такое решение получило TL.
соорудим дерево отрезков, где в каждой вершине у нас будет не декартово дерево, а сортированный массив. рядом с массивом структурка умеющая считать сумму на префиксе, и прибавлять единичку в любую позицию. дерево строится также как работает алгоритм сортировки слиянием.
думаю понятно как используя такую фиговину добавлять/удалять элементы.
(если мы решаем в прямом порядке (т.е. удаляем числа из перестановки) то нужно сначала массивы сумм проинициализировать единичками, а при удалении числа устанавливать эту единичку в нолик. для поиска кол-ва меньших делаем бинпоиск и суммируем на префиксе)
достаточно уметь считать количество чисел меньших и лежащих правее, т.к. количество чисел левее и больше можно вычислить исходя из информации о том сколько чисел сейчас всего, сколько правее, сколько правее и больше, сколько всего есть чисел меньше чем наше. (все это делается средствами нашего хитроумного дерева)
P.S. имхо задача кривая, у меня WA по ней все время. на рандомных тестах решение совпадает с лобовым.
UPD: а не, я кривой, не заметил что мультитест. теперь ТЛ
UPD2: у меня нерекурсивная оптимизированная реализация ТЛится, видимо есть быстрее решение чем логарифм в квадрате на эн
Я сдал эту фигню. С той же асимптотикой, но лучшей константой. Сортируем массив слиянием и одновременно подсчитываем для каждого элемента сколько чисел будет стоять справа от него и меньше чем оно само, в тот момент когда подойдёт очередь его удаления. идея такая же как подсчет инверсий с помощью сортировки слиянием, но нам нужно дерево отрезков для того чтобы отвечать сколько в некотором множестве чисел находится чисел больше заданного (и добавлять числа в это множество).
(не туда)