--->
2 задач
<---
Источники
Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.
В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.
На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).
Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.
Помогите Сергею.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — номера серверов, которым соответствуют точки восстановления (\(1 \le a_i \le m\)).
Третья строка входного файла содержит \(q\) — количество запросов, которые необходимо обработать (\(1 \le q \le 100\,000\)). В процессе обработки запросов необходимо поддерживать число \(p\), исходно оно равно 0. Каждый запрос задается парой чисел \(x_i\) и \(y_i\), используйте их для получения данных запроса следующим образом: \(l_i = \left((x_i + p) \bmod n\right) + 1\),
\(k_i = \left((y_i + p) \bmod m\right) + 1\) (\(1 \le l_i,x_i \le n\), \(1\le k_i, y_i \le m\)). Пусть ответ на \(i\)-й запрос равен \(r\). После выполнения этого запроса, следует присвоить \(p\) значение \(r\).
На каждый запрос выведите одно число — искомое минимальное \(r\), либо 0, если такого \(r\) не существует.
7 3 1 2 1 3 1 2 1 4 7 3 7 1 7 1 2 2
1 4 0 6
Генная инженерия это весело. Ученые собрали несколько ДНК и хотят создать из них что-то новое. Каждая ДНК может быть представлена в виде последовательности оснований \(A\), \(G\), \(T\), \(C\). Обозначим за \(DNA[a:b]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и заканчивающийся в индексе \(b\), и за \(DNA[a..]\) подотрезок последовательности оснований начинающийся в индексе \(a\) и идущий до конца последовательности. Ученые хотят производить следующие операции над последовательностью ДНК:
Исходные ДНК нумеруются от \(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