Задача №114323. Генетика
Генная инженерия это весело. Ученые собрали несколько ДНК и хотят создать из них что-то новое. Каждая ДНК может быть представлена в виде последовательности оснований \(A\), \(G\), \(T\), \(C\). Обозначим за \(DNA[a:b]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и заканчивающийся в индексе \(b\), и за \(DNA[a..]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и идущий до конца последовательности. Ученые хотят производить следующие операции над последовательностью ДНК:
- Операция скрещивания: ученые берут два ДНК \(DNA_1\) и \(DNA_2\) и числа \(k_1\) и \(k_2\). После этого они создают два новых ДНК: \(DNA_3 = DNA_1[1..k1] + DNA_2[k2+1..]\) и \(DNA_4 = DNA_2[1..k_2] + DNA_1[k_1+1..]\).
- Операция мутации – они берут ДНК, число \(k\) и одно из оснований. После этого они заменяют основание в позиции \(k\) выбранного ДНК на новое основание.
- Также иногда ученым интересно получать статистику о своих ДНК. Для этого они применяют операцию подсчёта – они берут ДНК и числа \(k_1\) и \(k_2\) (\(k_1 \le k_2\)). Они хотят узнавать количества оснований \(A\), \(G\), \(T\), \(C\) в \(DNA[k_1..k_2]\).
Исходные ДНК нумеруются от \(1\) до \(n\) где \(n\) - количество индексов. При создание новых ДНК они занимают два минимальных неиспользуемых натуральных индекса.
В первой строке содержится единственное число \(n\) (1 <= n <= 20) – количество исходных ДНК.
В последующих \(n\) строках содержится описание каждого ДНК – строка \(s_i\) состоящая из символов \(A\), \(G\), \(T\), \(C\) обозначающая \(i\)-е ДНК.
В следующей строке содержится единственное число \(q\) (1 <= q <= 30000)– количество операций, которые нужно выполнить.
В последующих \(q\) строках содержится описание операций, которые необходимо выполнить. Описание каждой операции задаётся в следующем форматe:
CROSS \(id_1\) \(id_2\) \(k_1\) \(k_2\), \(id_1\) != \(id_2\)
MUTATE \(id\) \(k\) \(m\)
COUNT \(id\) \(k_1\) \(k_2\)
\(id\) - индекс некоторого ДНК.
Длина каждой исходной ДНК не превышает 30000. Сумма длин ДНК, образованных в результате перекрестной операции, не будет превышать 2000000000. Общее количество ДНК не будет превышать 10000. Гарантируется, что все операции правильные.
Для каждой операции подсчёта выведите 4 числа: количества оснований \(A\), \(G\), \(T\), \(C\) соответсвенно в выбранном подотрезке данного ДНК.
Группа 0: Тест 1. 0 баллов
Группа 1: Тесты 2-6. 15 баллов. Дополнительные ограничения: длина любой ДНК не превосходит 1000. Для прохождения нужна группа 0
Группа 2: Тесты 7-11. 13 баллов. Дополнительные ограничения: Для всех запросов CROSS \(k_1\) = \(k_2\). Для прохождения нужна группа 1
Группа 3: Тесты 12-16. 23 балла. Дополнительные ограничения: отсутствует запрос MUTATE. Для прохождения нужна группа 1
Группа 4: Тесты 17-21. 14 баллов. Дополнительные ограничения: q <= 10000. Для прохождения нужны группы 2 и 3.
Группа 5: Тесты 22-26: 35 баллов. Дополнительных ограничений нет. Для прохождения нужна группа 4
2 CTCGC TGCGG 5 MUTATE 1 2 A COUNT 2 2 4 MUTATE 2 1 G CROSS 2 1 1 5 COUNT 4 3 6
0 2 0 1 0 2 0 2