Dadas and Friends

The key observation is that once a student becomes Dadas's friend, that student no longer affects the answer. Even if the student participates in later plays, the number of friends does not increase. Therefore, we can ignore students who are already friends.

We only maintain students who are not friends yet and may currently be in the classroom. Keep the following data.

• isFriend[i]: whether student $i$ is already Dadas's friend
• inRoom[i]: whether student $i$ is still not a friend and is currently considered to be in the classroom
• candidates: students who have entered the classroom since the last play and may still not be friends

Process the queries as follows.

• 1 i: If student $i$ is not a friend yet, mark inRoom[i] as true and add the student to candidates if needed.
• 2 i: If student $i$ is not a friend yet, mark inRoom[i] as false.
• 3: Check all students in candidates. Among them, only students who are still not friends and are currently marked as being in the classroom become new friends.
• 4: Print the current number of friends.

The same student may appear in candidates multiple times if the student enters and leaves repeatedly before a play happens. This is harmless because we check both isFriend and inRoom before increasing the answer.

The total number of elements ever added to candidates is at most the number of queries of type 1. Also, after every query of type 3, we clear candidates. Therefore, the total number of iterations over candidates throughout the whole program is $O(Q)$.

The total time complexity is $O(N+Q)$, and the memory usage is $O(N+Q)$.