트리와 가희
시간 제한1.5초메모리 제한512 MB
힙 방식으로 번호가 매겨진 완전 이진 트리에서 노드를 삭제해 가며 부분 트리 크기 질의와 부분 트리 삭제 질의를 처리한다.
문제
노드가 N개이고 루트 노드의 번호가 1인 완전 이진 트리가 있다. 루트 노드를 제외한 각 노드 i(i = 2, 3, 4, ..., N)의 부모는 ⌊i / 2⌋번 노드다. 다음 두 종류의 쿼리를 수행하는 프로그램을 작성하시오.
- 1 a : a를 루트로 하는 서브트리의 노드 개수를 출력한다. 노드 a가 존재하지 않으면 0을 출력한다.
- 2 a : a를 루트로 하는 서브트리를 제거한다. 노드 a가 존재하지 않으면 무시한다.
입력
첫째 줄에 완전 이진 트리의 노드 개수 N(1 ≤ N ≤ 1012111225)과 쿼리의 개수 Q(1 ≤ Q ≤ 361936)가 공백으로 구분되어 주어진다.
둘째 줄부터 Q개의 각 줄에는 문제에서 주어진 쿼리가 하나씩 주어진다. a는 1 이상 N 이하인 정수이며, 1번 쿼리는 최소한 하나 이상 주어지는 것이 보장된다.
출력
1번 쿼리에 대한 답을 한 줄에 하나씩 출력하라.