eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Персистентные структуры данных

Персистентные структуры данных

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Если вы не знаете, что такое персистентные структуры данных, то это не помешает вам решить эту задачу.

Персистентные структуры данных - это такие структуры данных, когда при любом изменении у нас остается доступ к предыдущим версиям этой структуры. Пусть у нас есть последовательность из n элементов, и нужно заменить p-й элемент. Для этого мы создаём новую версию структуры, которая отличается от предыдущей только p-м элементом. В результате у нас будет две версии последовательности.

В этой задаче вам необходимо просто посчитать количество версий последовательности, которые будут сохраняться в результате выполнения m запросов.

Входные данные

Первая строка содержит два числа n (1n100000) и m (1m100000), где n — количество чисел в последовательности, m - количество запросов.

Во второй строке задано n натуральных чисел - сама последовательность.

В следующих m строках заданы запросы двух типов:

  • SET i p d — из последовательности i образовать новую, где p-й элемент равен d;

  • GET i p — в последовательности i взять p-й элемент.

Начальная последовательность имеет номер 0. Позиции в последовательности начинаются с единицы. Запросов к несуществующим версиям не будет. При обработке запроса первого типа, создается новая версия, которая получает номер j+1, где j - номер последней добавленной последовательности, сначала j = 0.

Выходные данные

Выведите одно число - количество версий последовательности.

Пример

Входные данные #1
5 5
1 2 3 4 5
SET 0 3 7
GET 1 1
SET 0 5 6
SET 0 4 8
SET 0 5 8
Выходные данные #1
5
Автор Александр Цицюра