Откажемся от всех сложных структур. Заметим, что в массиве после всех операций будет O(k) подстрок исходного массива. То есть мы можем представить конечный массив как конкатенацию подстрок из начального массива ai1 + ai2 + ... + aik, где i1, i2, ..., ik — перестановка, k — количество подстрок.
После каждой операции будем в явном виде поддерживать массив перестановок i и блоков a. Введем вспомогательную операцию: разделить исходный массив в точке x, если x не является границей какого-либо блока, выполняем операцию за O(k). Рассмотрим как происходит операция первого типа. В начале и в конце каждого отрезка проведем операцию деления на блока, так мы суммарно добавили 4 отрезка или меньше. Теперь мы можем поменять местами блоки на этих отрезках за O(k) потому, что начала и концы отрезков точно находятся на границах блоков. Для запроса второго типа просто проведем операцию разреза.
Для выполнения операции второго типа выполним проход по всем операциям первого, что бы получить массив блоков, в котором после применения любого запроса блоки не будут создаваться, а будут только меняться местами. Вторым проходом по всем операциям будем отвечать на запросы. Теперь отсортируем числа внутри каждого блока и линейным проходом с бинарным поиском ответим на запрос за O(k·log n). Числа k не превышает 4·m, так как каждая операция добавляет не более 4-ех новых блоков.