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

「雅礼集训 2018 Day2」农民

题目描述

「搞 OI 不如种田。」

小 D 在家种了一棵二叉树,第 ii 个结点的权值为 aia_i

小 D 为自己种的树买了肥料,每天给树施肥。

可是几天后,小 D 却发现树上有几个结点枯死了,他这才发现,自己买的肥料是二叉搜索树专用版。

二叉搜索树是一种二叉树,满足每个结点的权值大于左子树内所有点的权值,小于右子树内所有点的权值。

二叉搜索树专用版肥料是这么工作的:首先,假设所有节点权值互不相同(小 D 的二叉树可能不满足),每种权值对应一种肥料,所有肥料会从根进入树中,如果一种肥料对应的权值等于当前结点权值,这种肥料会被当前结点完全吸收,否则若肥料对应的权值小于当前结点权值,肥料会流向左子树,否则流向右子树,如果流向的子树为空,肥料只好流失蒸发了。显然,如果树是二叉搜索树,所有节点都能吸收到肥料。

小 D 觉得自己还能抢救一下,他会进行若干次操作,每次操作修改一个点的权值或者翻转一个子树(子树内所有节点左右儿子互换)。在操作过程中,他有时会想知道一个点当前是否能吸收到肥料,以决定之后如何操作,请你帮帮可怜的小 D 吧。

输入格式

第一行两个正整数 n,mn, m,分别表示节点数和操作数。

接下来 nn 行,每行三个非负整数,其中第 ii 行第一个整数表示 aia_i,后两个数分别表示 ii 号点的左右儿子,没有则为 00

接下来 mm 行,每行先给出两个正整数 opt,x{\rm opt}, x。若 opt=1\rm opt = 1,接下来还有一个整数 yy,表示把结点 xx 的权值修改为 yy;若 opt=2\rm opt = 2,表示翻转以 xx 为根的子树;若 opt=3\rm opt = 3,表示查询 xx 号点是否能吸收到肥料。

输出格式

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

样例

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

数据范围与提示

对于全部数据, 1n,m105,0ai,y1091 \leq n, m \leq 10^5, 0 \leq a_i, y \leq 10^9

  • 子任务 1(points:20)\rm 1(points: 20)n,m5000n, m \leq 5000
  • 子任务 2(points:30)\rm 2(points: 30)opt2\rm opt \neq 2
  • 子任务 3(points:50)\rm 3(points: 50):无特殊限制