Записи і цикли#7321

Записи і цикли

1 секунда

64 мегабайти

Легка

У цій задачі вам потрібно створити бієкцію, яка відображає кожну перестановку довжини $n$ з $k$ циклами в перестановку тієї ж довжини з $k$ записами.

Перестановка $p$ довжини $n$ — це послідовність з $n$ цілих чисел $p (1), p (2), \dots, p (n)$ p(1), p(2), \ldots, p(n), де кожне число від $1$ до $n$ зустрічається рівно один раз.

Цикл у перестановці $p$ — це послідовність чисел $c_{1}, c_{2}, \dots, c_{m}$ c_1, c_2, \ldots, c_m, де $p (c_{1}) = c_{2}$ p(c_1) = c_2, $p (c_{2}) = c_{3}$ p(c_2) = c_3, $\dots$ , $p (c_{m}) = c_{1}$ p(c_m) = c_1. Особливий випадок — цикл одиничної довжини: $p (i) = i$ p(i) = i. Кожна перестановка може бути представлена як об'єднання попарно неперетинних циклів.

Записом у перестановці $p$ називається такий її елемент $p_{j}$ p_j, який більший за всі попередні елементи: $p_{j} > p_{i}$ p_j > p_i для кожного $i < j$ i < j. За визначенням, $p_{1}$ p_1 завжди є записом. Доведено, що для заданих $n$ і $k$ кількість перестановок довжини $n$ з $k$ циклами дорівнює кількості перестановок довжини $n$ з $k$ записами. Отже, існує бієкція між перестановками довжини $n$ з $k$ циклами і перестановками довжини $n$ з $k$ записами. Бієкція — це функція, яка встановлює взаємно однозначну відповідність між елементами двох множин: кожному елементу першої множини відповідає рівно один елемент другої множини, і навпаки. Вам потрібно знайти і реалізувати таку функцію.

Вхідні дані

Перший рядок містить кількість перестановок $t$ ( $1 \leq t \leq 300000$ 1 \le t \le 300\,000).

Кожен з наступних $t$ рядків описує одну перестановку. Опис починається з числа $n$ ( $1 \leq n \leq 300000$ 1 \le n \le 300\,000) — довжини перестановки, за яким слідує символ "r" або "c", що вказує на тип перестановки. Далі йде послідовність з $n$ цілих чисел, що задають саму перестановку. Кожне число від $1$ до $n$ зустрічається в цій послідовності тільки один раз.

Елементи в рядку розділені пробілами. Загальна довжина всіх вхідних перестановок не перевищує $300000$ .

Вихідні дані

Формат виходу такий самий, як і вхідних даних.

Перший рядок містить кількість вхідних перестановок $t$ .

Для кожної з $t$ заданих перестановок виведіть відповідну перестановку в окремому рядку. Якщо тип вхідної перестановки — "r", знайдіть кількість записів у ній і виведіть відповідну перестановку типу "c" з такою ж кількістю циклів. Якщо тип вхідної перестановки — "c", знайдіть кількість циклів у ній і виведіть відповідну перестановку типу "r" з такою ж кількістю записів.

Кожен з $t$ рядків починається числом $n$ — довжиною перестановки, за яким слідує символ, що вказує на тип. Далі йдуть $n$ чисел, що описують саму перестановку. Елементи в одному рядку розділяються одним пробілом.

Відповідність має бути узгодженою: якщо перестановці $p$ типу "r" відповідає перестановка $q$ типу "c", то зворотне також має бути вірним, жодна інша перестановка типу "c" не може відповідати $p$ , і жодна інша перестановка типу "r" не може відповідати $q$ . Ваша бієкція не обов’язково має бути узгодженою з різними тестами.

Приклади

Приклад 1

Примітка

Довжина першої перестановки $n = 3$ n = 3. Перша перестановка має тип "r" і містить три записи. Друга перестановка має тип "c" і містить три цикли. Ці дві перестановки відповідають одна одній. Третя і четверта перестановки мають тип "r" і містять по два записи кожна. П’ята перестановка має тип "c" і містить два цикли. Вона відповідає третій перестановці. Четверта перестановка відповідає перестановці $3, 2, 1$ типу "c", що містить два цикли.

Остання перестановка має довжину $n = 2$ n = 2, тип "c" і складається з одного циклу. Вона відповідає перестановці $2, 1$ типу "r" з одним записом.

Зазначимо, що це не єдина можлива бієкція: у прикладі дано альтернативний варіант виходу. Для третьої вхідної перестановки ( $2, 1, 3$ типу "r") ми обрали $3, 2, 1$ типу "c" як відповідну. Тоді четверта перестановка ( $2, 3, 1$ типу "r") повинна мати іншу відповідну перестановку, тому оберемо для неї перестановку $1, 3, 2$ типу "c". Для п’ятої перестановки ( $2, 1, 3$ типу "c") єдино можливою є $1, 3, 2$ типу "r", оскільки дві інші перестановки з двома записами вже відповідають іншим перестановкам з двома циклами.