#6498. 「雅礼集训 2018 Day2」农民

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

「搞 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 号点是否能吸收到肥料。

输出格式

对于每个询问,输出一行 YESNO 表示答案。

样例

样例输入 1

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

样例输出 1

YES
YES
NO
YES
NO

数据范围与提示

对于全部数据, 1 \leq n, m \leq 10^5, 0 \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) :无特殊限制