다다스와 친구들

핵심은 이미 다다스의 친구가 된 학생은 이후 정답에 더 이상 영향을 주지 않는다는 점이다. 한 번 친구가 된 학생은 다시 놀이에 참여해도 친구 수를 증가시키지 않는다. 따라서 이미 친구가 된 학생은 이후 쿼리에서 무시해도 된다.

아직 친구가 아니면서 현재 교실에 있을 가능성이 있는 학생들만 관리하자. 이를 위해 다음 정보를 유지한다.

• isFriend[i]: $i$번 학생이 이미 다다스의 친구인지 여부
• inRoom[i]: $i$번 학생이 아직 친구가 아니며, 현재 교실에 있다고 관리되고 있는지 여부
• candidates: 마지막 놀이 이후 교실에 들어온 적이 있는, 아직 친구가 아닐 수 있는 학생들의 목록

쿼리를 다음과 같이 처리한다.

• 1 i: $i$번 학생이 아직 친구가 아니라면 inRoom[i]를 참으로 만들고, 필요하면 candidates에 넣는다.
• 2 i: $i$번 학생이 아직 친구가 아니라면 inRoom[i]를 거짓으로 만든다.
• 3: candidates에 들어 있는 학생들을 확인한다. 그중 아직 친구가 아니고 현재 교실에 있다고 표시된 학생만 새 친구가 된다.
• 4: 현재 친구 수를 출력한다.

한 학생이 놀이가 일어나기 전까지 교실에 들어오고 나가기를 반복할 수 있으므로 candidates에 같은 학생이 여러 번 들어갈 수 있다. 하지만 실제로 친구 수를 증가시킬 때는 isFriend와 inRoom을 확인하므로 중복은 문제가 되지 않는다.

중요한 점은 candidates에 들어간 원소의 총 개수가 전체 1번 쿼리 수를 넘지 않는다는 것이다. 또한 3번 쿼리마다 candidates를 비우므로, 전체 실행 동안 candidates를 순회하는 총 횟수는 $O(Q)$이다.

따라서 전체 시간 복잡도는 $O(N+Q)$이고, 메모리 사용량은 $O(N+Q)$이다.