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

[passat]

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

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

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

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

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

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

[volvo]

passat, а тебе что, обязательно какая-то

хитрая структура

нужна? У тебя ограничения на используемую память есть? Компилятор какой? Вот тебе простейшее решение (тестировалось на FPC), 2 массива (обычных, статических массива, тест гонялся на размерах 100-200 тысяч + несколько сот тысяч перестановок) нужного размера + встроенный Move... Выигрыш относительно списков - более 2.5 раз (точнее - 2.62 .. 2.68, на разных значениях transform_count)

  for i := 1 to arrsize do begin
    arr1[i] := i; arr2[i] := 0;
  end;
  _from := @arr1; _to := @arr2;

  for i := 1 to transform_count do begin
    // тут получаешь transform_start_pos, transform_finish_pos для итерации #I
    _to^ := _from^;
    pp := transform_finish_pos - transform_start_pos + 1;
    move(_from^[transform_start_pos], _to^[1], pp*sizeof(longint));
    move(_from^[1], _to^[pp+1], (transform_start_pos - 1)*sizeof(longint));

    p := _from; _from := _to; _to := p;
  end;
// в результате - в _from^ лежит результат всех этих действий...

[passat]

Компилятор Delphi 7 или Free Pascal. Либо на C++ MS VisualStudio до 2005 включительно. Язык, вообще говоря, не принципиален.
Ограничений по памяти вроде нет.

А за счет чего получается выигрыш в сравнении со списком? Тут же мы имеем время n^2, правильно?

Оптимизированное даже по трем итераторам на линейном списке решение не проходит проверку на время. Вложенные списки дают выигрыш кое-где, но все тесты все равно не проходит . Видать, тесты подобраны так, что вложенный список быстро вырождается в линейный и тогда получаем даже проигрыш.
Данные по времени выполнения сервер печатает странные: тесты с большим временем принимает, а с меньшим - нет. То ли сервер слишком умный, то ли я отсталый.

За подсказку спасибо. Реализацию уже почти добил, надо попробовать сдать. Но к сожалению что-то подсказывает, что этого может быть недостаточно.

А есть ли структура, которая работает за логарифмическое время? Хотя б ссылку на это чудо... А то горю

Заранее спасибо.

ПС. А не получится ли в случае, если решение все же пройдет, зависимое от языка решение?

Сообщение отредактировано: passat - 28.04.2009 12:52

[passat]

Не прошла задачка по времени. А жаль.

Видимо, есть все же какая-то структура с логарифмическим временем доступа. Чисто теоретически это должно быть какое-то дерево, но непонятно какое. И как его строить.