Персистентные структуры данных
Если вы не знаете, что такое персистентные структуры данных, то это не помешает вам решить эту задачу.
Персистентные структуры данных - это такие структуры данных, когда при любом изменении у нас остается доступ к предыдущим версиям этой структуры. Пусть у нас есть последовательность из n элементов, и нужно заменить p-й элемент. Для этого мы создаём новую версию структуры, которая отличается от предыдущей только p-м элементом. В результате у нас будет две версии последовательности.
В этой задаче вам необходимо просто посчитать количество версий последовательности, которые будут сохраняться в результате выполнения m запросов.
Входные данные
Первая строка содержит два числа n (1 ≤ n ≤ 100000) и m (1 ≤ m ≤ 100000), где n — количество чисел в последовательности, m - количество запросов.
Во второй строке задано n натуральных чисел - сама последовательность.
В следующих m строках заданы запросы двух типов:
SET i p d — из последовательности i образовать новую, где p-й элемент равен d;
GET i p — в последовательности i взять p-й элемент.
Начальная последовательность имеет номер 0. Позиции в последовательности начинаются с единицы. Запросов к несуществующим версиям не будет. При обработке запроса первого типа, создается новая версия, которая получает номер j+1, где j - номер последней добавленной последовательности, сначала j = 0.
Выходные данные
Выведите одно число - количество версий последовательности.