Tree and Gahui
Time limit1.5sMemory limit512 MB
In a heap-indexed complete binary tree, answer subtree-size queries and subtree-removal queries as nodes get deleted over time.
- Level
Medium7 of 10
- Topics
- Tree, Segment tree, Binary search, Implementation
- Solved
- No attempts yet
Problem
There is a complete binary tree with N nodes whose root is node 1. For every node i other than the root (i = 2, 3, 4, ..., N), its parent is node ⌊i / 2⌋. Write a program that handles the following two kinds of queries.
- 1 a : Print the number of nodes in the subtree rooted at a. If node a does not exist, print 0.
- 2 a : Remove the subtree rooted at a. If node a does not exist, ignore the query.
Input
The first line gives the number of nodes N (1 ≤ N ≤ 1012111225) and the number of queries Q (1 ≤ Q ≤ 361936), separated by a space.
Each of the next Q lines contains one query as described in the problem. a is an integer between 1 and N inclusive, and at least one type 1 query is guaranteed to appear.
Output
Print the answers to the type 1 queries, one per line.