Перестановка участков последовательности Опции

[passat]

Помогите еще с одной задачкой.
Имеется последовательность натуральных чисел.
Необходимо выполнить N перестановок участков последовательности, где участок задается его началом и концом. Перестановка выполняется в начало последовательности.

Т.е. для последовательности из 6 чисел ип трех перестановках
2 4
2 4
4 4

результат должен быть 2 3 4 1 5 6 .

Количество чисел и перестановок может быть несколько сот тысяч.

Первая идея: список. В связи с чем вопрос: можно ли как-то оптимизировать порядок выполнения перестановок? Либо хотя бы порядок переброски итераторов?

Или же существует еще какое-то более интересное решение?

[volvo]

резко возрастет скорость переброски итераторов

За счет чего?

[passat]

Положим, что количество элементов 10000 и каждый вложенный список имеет 100 элементов. Тогда к последнему доберемся за 100+100 = 200 шагов., что в 50раз меньше. Естесственно, придется пожертвовать тем, что вместо одной перестановки участков придется выполнить, к примеру, три.

Конечно, к концу перестановок наверняка вложенный список выродится в линейный, но... других решений, кроме введения в рассмотрение еще и внутреннего итератора и анализа положения начала и конца участка относительно этих трех итераторов (долго и скучно), пока не вижу .

Потому и спрашиваю, что, возможно, существует более остроумное решение.

[passat]

На линейном списке превышен предел времени исполнения. Тратит приблизительно 4сек. Это с оптимизацией относительно начала/конца списка. Можно, конечно, попробовать оптимизацию относительно еще среднего итератора, но, боюсь, данные подобраны так, что не прокатит.
На вложенном списке без оптимизации положение улучшается только на некоторых тестах - реальный выигрыш во времени в 3-7раз. Но все равно пару тестов не проходят.

Чую, есть какая-то хитрая структура, позволяющая перебрасывать итераторы за логарифмическое время, но не знаю какая.

Помогите, пожалуйста. Нужно срочно.

Сообщение отредактировано: passat - 25.04.2009 14:57