P10990 [蓝桥杯 2023 国 Python A] 彩色二叉树
题目背景
建议使用 PyPy3 提交本题。
题目描述
给定包含 $n$ 个结点的完全二叉树，如下图是一棵包含 $n = 6$ 个结点的完全二叉树。
**树上的所有节点开始时没有被染色，颜色为 $0$。**
给定 $q$ 次操作，操作可以是：
1. $x_i\ y_i\ z_i$，表示将与结点 $x_i$ 距离小于等于 $y_i$ 的结点的颜色全部染成 $z_i$；
1. $x_i$，表示查询结点 $x_i$ 的颜色。
输入格式
输入的第一行包含两个整数 $n, q$，用一个空格分隔。
接下来 $q$ 行，每行包含 $1$ 个操作，相邻的整数之间使用一个空格分隔。保证每个操作都是合法的。
输出格式
对于每个查询操作，输出一行包含一个整数表示对应的答案。
说明/提示
对于 $40\%$ 的评测用例，$n, q \le 5000$；
对于所有评测用例，$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$。