P4940「雅礼集训 2018 Day2」农民 | ||
|
问题描述
「搞 OI 不如种田。」
小 D 在家种了一棵二叉树,第 \(i\) 个结点的权值为 \(a_i\)。
小 D 为自己种的树买了肥料,每天给树施肥。
可是几天后,小 D 却发现树上有几个结点枯死了,他这才发现,自己买的肥料是二叉搜索树专用版。
二叉搜索树是一种二叉树,满足每个结点的权值大于左子树内所有点的权值,小于右子树内所有点的权值。
二叉搜索树专用版肥料是这么工作的:首先,假设所有节点权值互不相同(小 D 的二叉树可能不满足),每种权值对应一种肥料,所有肥料会从根进入树中,如果一种肥料对应的权值等于当前结点权值,这种肥料会被当前结点完全吸收,否则若肥料对应的权值小于当前结点权值,肥料会流向左子树,否则流向右子树,如果流向的子树为空,肥料只好流失蒸发了。显然,如果树是二叉搜索树,所有节点都能吸收到肥料。
小 D 觉得自己还能抢救一下,他会进行若干次操作,每次操作修改一个点的权值或者翻转一个子树(子树内所有节点左右儿子互换)。在操作过程中,他有时会想知道一个点当前是否能吸收到肥料,以决定之后如何操作,请你帮帮可怜的小 D 吧。
输入格式
第一行两个正整数 \(n, m\),分别表示节点数和操作数。
接下来 \(n\) 行,每行三个非负整数,其中第 \(i\) 行第一个整数表示 \(a_i\),后两个数分别表示 \(i\) 号点的左右儿子,没有则为 $0$。
接下来 \(m\) 行,每行先给出两个正整数 \({\rm opt}, x\)。
若 \(\rm opt = 1\),接下来还有一个整数 \(y\),表示把结点 \(x\) 的权值修改为 \(y\);
若 \(\rm opt = 2\),表示翻转以 \(x\) 为根的子树;
若 \(\rm opt = 3\),表示查询 \(x\) 号点是否能吸收到肥料。
输出格式
对于每个询问,输出一行 YES
或 NO
表示答案。
样例输入
3 7
10 2 3
5 0 0
5 0 0
3 1
3 2
3 3
1 3 100
3 3
2 1
3 3
样例输出
YES
YES
NO
YES
NO
提示
对于全部数据, $1 \leq n, m \leq 10^5, 1 \leq a_i, y \leq 10^9$。
- 子任务 \(\rm 1(points: 20)\):\(n, m \leq 5000\)
- 子任务 \(\rm 2(points: 30)\):\(\rm opt \neq 2\)
- 子任务 \(\rm 3(points: 50)\):无特殊限制