Персистентні структури даних#5626
Якщо ви не знаєте, що таке персистентні структури даних, не хвилюйтеся — це не завадить вам розв'язати цю задачу.
Персистентні структури даних — це такі структури даних, які дозволяють отримувати доступ до попередніх версій структури навіть після змін. Припустимо, у вас є послідовність із елементів, і потрібно замінити -ий елемент. Для цього створюється нова версія структури, яка відрізняється від попередньої лише -им елементом. У результаті у вас буде дві версії послідовності.
У цій задачі вам потрібно просто порахувати кількість версій послідовності, які буде збережено в результаті виконання запитів.
Перший рядок містить два числа (1 \leq n \leq 100\,000) та (1 \leq m \leq 100\,000), де — кількість чисел у послідовності, — кількість запитів.
Другий рядок містить натуральних чисел — саму послідовність.
Кожен із наступних рядків містить один із наступних запитів:
SET i p d — створити нову послідовність з послідовності , де -ий елемент дорівнює ;
GET i p — у послідовності взяти -ий елемент.
Початкова послідовність має номер . Позиції в послідовності нумеруються з одиниці. Запитів до неіснуючих версій не буде. При обробці запиту першого типу створюється нова версія, яка отримує номер j+1, де — номер останньої доданої послідовності, спочатку j = 0.
Виведіть одне число — кількість версій послідовності.
Приклад 1