Доброго времени суток. Есть такая задача — Лыжные гонки. Your text to link here...
Во время лыжных соревнований N спортсменов стартуют с интервалом в 1 минуту. Скорость каждого лыжника на дистанции постоянна: i-й лыжник преодолевает 1 км за wi минут. Длина трассы равна L км. Считается, что i-й лыжник обогнал j-го (совершил обгон), если он стартовал позже j-го, а пришёл к финишу раньше него. Подсчитайте суммарное число совершённых во время гонки обгонов.
Входные данные
Первая строка входного файла содержит два целых числа N и L. Во второй строке через пробел расположены N целых чисел wi.
1<=N<=500000, 1<=L<=10^9, 1<=Wi<=10^9
Выходные данные
Выведите единственное число — суммарное количество обгонов.
Ограничение по времени — 2 сек Ограничение по памяти — 128\256 мб(не нашёл информации)
Что я придумал по этой задаче : будем идти по порядку, увеличивая i. i лыжник обгонит j, если i>j и L*Wi < L*Wj-(i-j). Что из этого следует — будем хранить в каждой вершине дерева отрезков отсотрированный массив, который относится к этой части ДО (деревом Ропана это вроде зовётся). И потом на каждый запрос мы будем log(N)*log(n) отвечать на этот запрос, сколько есть таких чисел на отрезке [1;i-1]. И на каждой итерации мы будем отнимать единицу от отрезка предыдущего.
Но квадрат логарифма судя по всему не зайдет. А логарифм зайдет. Как я придумал, тут нужно писать каскадирование. Это нам по идее обеспечит нужную асимптотику.
В чём вопрос : верна ли эта мысль? Если верна, то можете ли рассказать подробнее про это самое каскадирование и как его писать, если можно. Я ни разу его не писал и смутно представляю, как это сделать.
И ещё — нет ли других решений данной задачи?
Заранее спасибо.
Дам одну подсказку: это задача на поиск количества инверсий.
Насчёт вашей подсказки насчёт инверсий. я с такими задачами плохо знаком, подозреваю, что тут дерево фенвика... но как это сделать — понятия не имею. была идея, что для каждого числа надо свою ячейку массива, и потом уже по этому массиву фенвика пускать. но тут же нужны запросы модификации... да и если делать сжатие координат, то непонятно, что там дальше делать
Пронумеруем лыжников от 1 до n в том порядке, в котором они стартуют. Теперь найдём в каком порядке они финишировали. Для этого нужно отсортировать по возрастанию времени финиша массив пар (номер лыжника, время финиша). В получившемся массиве надо найти количество инверсий (количество пар индексов i, j, таких что i < j и a[i] > a[j]). Это можно сделать с помощью немного изменённой сортировки слиянием, прочитать об этом можно, например, тут.