Персистентні структури даних
Персистентні структури даних
Якщо ви не знаєте, що таке персистентні структури даних, то це не перешкодить вам розв'язати цю задачу.
Персистентні структури даних — це такі структури даних, що при будь-якій зміні у нас залишається доступ до попередніх версій цієї структури. Нехай у нас є послідовність із 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.
Вихідні дані
Виведіть одне число - кількість версій послідовності.
Приклад
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
5