P10990 [Lanqiao Cup 2023 National Python A] Colored Binary Tree

It is recommended to use PyPy3 to submit this problem.

Given a complete binary tree with $n$ nodes. The figure below shows a complete binary tree with $n = 6$ nodes. **All nodes on the tree are initially uncolored, with color $0$.**  There are $q$ operations. Each operation can be: 1. $x_i\ y_i\ z_i$: set the color of all nodes whose distance to node $x_i$ is less than or equal to $y_i$ to $z_i$. 1. $x_i$: query the color of node $x_i$.

The first line contains two integers $n, q$, separated by a space. In the next $q$ lines, each line contains one operation, and adjacent integers are separated by a space. It is guaranteed that every operation is valid.

For each query operation, output one line containing one integer representing the corresponding answer.

For $40\%$ of the testdata, $n, q \le 5000$. For all testdata, $1 \le n \le 10^6$, $1 \le q \le 2 \times 10^5$, $1 \le x_i \le n$, $1 \le y_i \le 10^6$, $1 \le z_i \le 10^6$. Translated by ChatGPT 5