Задачи
Записи и циклы
Записи и циклы
В этой задаче Вам следует построить биекцию биекцию, отображающую каждую перестановку длины \textbf{n }с \textbf{k }циклами в перестановку длины \textbf{n} с \textbf{k} записями.
Перестановкой \textbf{p} длины \textbf{n} называется последовательность из \textbf{n} целых чисел \textbf{p}(\textbf{1}), \textbf{p}(\textbf{2}), ..., \textbf{p}(\textbf{n}) таких что каждое из чисел \textbf{1}, \textbf{2}, ..., \textbf{n} встречается в последовательности ровно один раз.
Циклом в перестановке \textbf{p} называется последовательность чисел \textbf{c_1}, \textbf{c_2}, ..., \textbf{c_m} таких что \textbf{p}(\textbf{c_1}) = \textbf{c_2}, \textbf{p}(\textbf{c_2}) = \textbf{c_3}, ..., \textbf{p}(\textbf{c_m}) = \textbf{c_1}. Особый случай представляет собой цикл единичной длины: \textbf{p}(\textbf{i}) = \textbf{i}. Можно показать, что каждая перестановка может быть представлена как объединение попарно непересекающихся циклов.
Записью, или значением записи в перестановке \textbf{p} называется такой ее элемент \textbf{p_j}, который больше всех ее предшествующих элементов: \textbf{p_j} > \textbf{p_i} для каждого \textbf{i} < \textbf{j}. Отметим, что \textbf{p_1} всегда является записью по определению. Можно доказать, что для заданных \textbf{n} и \textbf{k} количество перестановок длины \textbf{n} с \textbf{k} циклами равно количеству перестановок длины \textbf{n} с \textbf{k} записями. Поэтому существует биекция, отображающая перестановки длины \textbf{n} с \textbf{k} циклами в перестановки длины \textbf{n} с \textbf{k} записями и наоборот. Биекцией называется функция, которая ставит во взаимно однозначное соответствие элементы двух множеств: каждому элементу первого множества поставлен в соответствие в точности один элемент второго множества, а каждому элементу второго множества поставлен в соответствие в точности один элемент первого множества. Вам следует найти и реализовать такую функцию.
\InputFile
Первая строка содержит количество перестановок \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{300 000}).
Каждая из следующих \textbf{t} строк содержит описание одной перестановки. Описание стартует числом \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{300 000}) - длиной перестановки, за которым следует символ “\textbf{r}” или “\textbf{c}” указывающий на тип перестановки. Далее следует последовательность из \textbf{n} целых чисел, задающих саму перестановку. Каждое число от \textbf{1} до \textbf{n} встречается в этой последовательности только один раз.
Последовательные элементы в строке разделены пробелами. Общая длина всех входных перестановок не превосходит \textbf{300 000}.
\OutputFile
Имеет такой же формат как и входные данные.
Первая строка содержит количество входных перестановок \textbf{t}.
Для каждой из \textbf{t} заданных перестановок вывести соответствующую ей перестановку в отдельной строке. Если тип входной перестановки “\textbf{r}”, найдите количество записей в ней и выведите соответствующую ей перестановку типа “\textbf{c}” с таким же количеством циклов. Если тип входной перестановки “\textbf{c}”, найдите количество циклов в ней и выведите соответствующую ей перестановку типа “\textbf{r}” с таким же количеством записей.
Каждая из \textbf{t} строк начинается числом \textbf{n} - длиной перестановки, за которой следует символ указывающий на тип. Далее следуют \textbf{n} чисел, описывающих саму перестановку. Последовательные токены в одной строке разделять одним пробелом.
Соответствие должно быть согласующимся: если перестановке \textbf{p} типа “\textbf{r}” соответствует перестановка \textbf{q} типа “\textbf{c}”, то обратное также должно быть верным, никакая другая перестановка типа “\textbf{c}” не может соответствовать \textbf{p}, и никакая другая перестановка типа “\textbf{r}” не может соответствовать \textbf{q}. Ваша биекция не обязательно должна быть согласующейся с различными тестами.
\Note
Длина первой перестановки \textbf{n} = \textbf{3}. Первая перестановка имеет тип “\textbf{r}” и содержит три записи. Вторая перестановка имеет тип “\textbf{c}” и содержит три цикла. Эти две перестановки соответствуют друг другу. Третья и четвертая перестановки имеют тип “\textbf{r}” и содержат каждая по две записи. Пятая перестановка имеет тип “\textbf{c}” и содержит два цикла. Она соответствует третьей перестановке. Четвертая перестановка соответствует перестановке \textbf{3}, \textbf{2}, \textbf{1} типа “\textbf{c}”, содержащей два цикла.
Последняя перестановка имеет длину \textbf{n} = \textbf{2}, тип “\textbf{c}” и состоит из одного цикла. Она соответствует перестановке \textbf{2}, \textbf{1} типа “\textbf{r}” с одной записью.
Отметим, что это не единственная возможная биекция: в примере дан альтернативный вариан выхода. Для третьей входной перестановки (\textbf{2}, \textbf{1}, \textbf{3} типа “\textbf{r}”) мы выбрали \textbf{3}, \textbf{2}, \textbf{1} типа “\textbf{c}” как соответствующую. Тогда четвертая перестановка (\textbf{2}, \textbf{3}, \textbf{1} типа “\textbf{r}”) должна иметь другую соответствующую перестановку, поэтому выберем для нее перестановку \textbf{1}, \textbf{3}, \textbf{2} типа “\textbf{c}”. Для пятой перестановки (\textbf{2}, \textbf{1}, \textbf{3} типа “\textbf{c}”) единственно воззможной является \textbf{1}, \textbf{3}, \textbf{2} типа “\textbf{r}”, так как две другие перестановки с двумя записями уже соответствуют другим перестановкам с двумя циклами.
Входные данные #1
6 3 r 1 2 3 3 c 1 2 3 3 r 2 1 3 3 r 2 3 1 3 c 2 1 3 2 c 2 1
Выходные данные #1
6 3 c 1 2 3 3 r 1 2 3 3 c 2 1 3 3 c 3 2 1 3 r 2 1 3 2 r 2 1