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

[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^ лежит результат всех этих действий...