Persistent Data Structures#5626
If you're not familiar with persistent data structures, don't worry—you can still solve this problem.
Persistent data structures are those that allow you to access previous versions of the structure even after modifications. Imagine you have a sequence of elements, and you need to replace the -th element. To do this, you create a new version of the structure that is identical to the previous one, except for the -th element. Consequently, you end up with two versions of the sequence.
In this problem, your task is to count how many versions of the sequence will be stored after executing queries.
The first line contains two integers (1 \leq n \leq 100\,000) and (1 \leq m \leq 100\,000), where is the number of elements in the sequence, and is the number of queries.
The second line contains natural numbers, representing the sequence itself.
Each of the next lines contains one of the following queries:
SET — create a new sequence from sequence , where the -th element is set to ;
GET — retrieve the -th element from sequence .
The initial sequence is numbered . Positions in the sequence start from one. There will be no queries for non-existent versions. When processing a query of the first type, a new version is created, which is assigned the number j+1, where is the number of the last added sequence, starting with j = 0.
Output a single number—the total number of versions of the sequence.
Example 1