Автор задачи: Даниил Орешников, разработчик: Павел Скобелин
Давайте воспользуемся декартовым деревом для решения задачи. Будем поддерживать декартово дерево по неявному ключу из текущих сегментов, каждый из которых также будет декартовым деревом по неявному ключу, в котором будем хранить сами элементы очереди в нужном порядке. Научимся обрабатывать запросы всех типов:
Таким образом эту задачу можно решать с помощью вложенных ДД.
Также есть решение, не использующее декартово дерево или хотя бы два вложенных ДД. Давайте хранить все элементы очереди в обычном массиве и помечать уже использованные элементы.
Тогда сегменты можно хранить в виде встроенного дерева поиска (например, ordered_set в C++, или также в декартовом дереве, в данном решении оно будет одномерное). Каждый сегмент будет задаваться парой чисел: индекс его начала в текущем массиве и количество элементов в нем. Тогда решение остается таким же, но нужно по другому обрабатывать запрос номер три.
Теперь тяжело искать индекс начала второго сегмента, если мы разрежем сегмент после $$$i$$$-го элемента. Заметим, что тогда индекс начала нужного сегмента будет индексом $$$i+1$$$-й единицы, начиная с индекса начала текущего сегмента. Этот запрос, например, можно обрабатывать техникой спуска по дереву отрезков. Тогда если поддерживать использованные элементы в дереве отрезков, то мы сможем эффективно отвечать на все запросы.