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
Автор Олександр Цицюра