alino4ka2012

11.06.2023 21:25

Информатика

Есть ответ 👍

Слияние отрезков
Даны два отсортированных массива A, B. Нужно обработать запросы следующего вида:

1 l r - Удалить подотрезок A[l, r], добавить его в конец B, и затем отсортировать B.

2 l r - Удалить подотрезок B[l, r], добавить его в конец A, и затем отсортировать A.

Необходимо вывести получившиеся массивы A, B.

Формат входных данных
Первая строка ввода содержит одно целое число N (0 ≤ N ≤ 5*105) - размер массива A.

Вторая строка содержит N целых чисел ai (1 ≤ a1 ≤ a2 ≤ ... ≤ an ≤ 109) - содержимое массива A.

Третья строка ввода содержит одно целое число M (0 ≤ M ≤ 5*105) - размер массива B.

Четвёртая строка содержит M целых чисел bi (1 ≤ b1 ≤ b2 ≤ ... ≤ bm ≤ 109) - содержимое массива B.

Пятая строка ввода содержит одно целое число Q (1 ≤ Q ≤ 9*105) - число запросов.

Следующие Q строк содержат по три целых числа t, l, r (t равно 1 или 2, 1 ≤ l ≤ r) - описание очередного запроса.

Гарантируется, что все запросы корректны, то есть при t = 1 всегда существует A[l, r] и при t = 2 всегда существует B[l, r].

Формат результата
В первой строке вывода должно быть одно целое число N' - итоговый размер массива A.

Во второй строке вывода должны быть N' целых чисел - содержимое итогового массива A.

В третьей строке вывода должно быть одно целое число M' - итоговый размер массива B.

В четвёртой строке вывода должны быть M' целых чисел- содержимое итогового массива B.

Примеры
Входные данные
4
1 3 5 7
5
2 4 6 7 8
5
1 1 1
2 2 4
2 1 3
1 1 7
2 2 5
Результат работы
6
2 3 4 5 7 8
3
1 6 7
Входные данные
1
1
0

1
1 1 1
Результат работы
0

1
1
Примечания
Рассмотрим первый пример из условия:
После первого запроса A = [3, 5, 7], B = [1, 2, 4, 6, 7, 8];
После второго запроса A = [2, 3, 4, 5, 6, 7], B = [1, 7, 8];
После третьего запроса A = [1, 2, 3, 4, 5, 6, 7, 7, 8], B = [];
После четвёртого запроса A = [7, 8], B = [1, 2, 3, 4, 5, 6, 7];
После пятого запроса A = [2, 3, 4, 5, 7, 8], B = [1, 6, 7].