← 返回题目列表

AtCoder · discovery_2016_final_e

E. 你可以创建一个令人惊叹的二叉搜索树!

中文机器翻译题面 查看原题

問題文

您正在接受 DISCO 的采访。面试前 由 0 节点组成的二叉搜索树 您已获得 T 。

您将从面试官处收到以下信息: 您收到的任务是按给定顺序处理 Q 查询。你是 我决定通过快速处理 Q 查询来给面试官一个惊喜。

查询类型如下所示。

  1. 1 v : T 有一个值 在适当的位置插入一个节点 v 。
  2. 2 v : T 中包含的值为 v 一个节点使得 u 的左子树 lst 和右子树 对于 rst ,高度差 如果 h(lst) - h(rst) 。
  3. 3 v : T 中包含的值为 v 一个节点使得 u 有左子节点, 向右旋转 u 。如果左子节点不存在 如果-1。
  4. 4 v : T 中包含的值为 v 一个节点使得 u 有右子节点, 向左旋转 u 。如果右子节点不存在-1。

以上类型 在 1 查询中,值为 一个节点使得 v 是 保证不存在于 T 中。 以上类型 保证存在于 2,3,4 查询中,值为 一个节点使得 v 是 保证不存在于 T 中。


  • 这里,二叉搜索树 T 的高度定义如下。

    • 一个节点 以 u 为根的二叉搜索树的高度 h(u) 是 u 的左子树 lst 和 将其放在 u 的右子树 由 rst 当 h(u) = max(h(lst), h(rst))+1 代表。 左子树到
    • 在这里, u 如果 lst 不存在, 视为 h(lst) = 0 。
    • 同样, u 的右子树 rst 不存在, 视为 h(rst) = 0 。
  • 二分探索木 T 到节点 插入 u 的操作执行如下。注意这个操作的结果是 当给出 T 和 将其放在 u 时,保证唯一确定。 当它由

    1. T 是 从 0 节点组成时, 创建以 T 从 u 为根的二叉搜索树并结束该过程。 当它由
    2. T 是 从 1 或更多节点组成时,满足以下条件。 使 u 成为节点的子节点并结束进程。

      • 一个节点 以 w 最多只能拥有直系子代的数量。 2 (分别称为左子节点和右子节点)。
      • 一个节点 以 w 左后代节点所持有的任何值 小于 w 的值。
      • 一个节点 以 w 右后代节点所持有的任何值 它大于或等于 w 的值。
  • 二分探索木 T 中包含的节点 u 的右旋转执行如下。这个操作 当 u 的左子节点不存在时,无法执行此操作。

    1. u 的左子级 l 。 删除连接
    2. u 和 将其放在 l 的边。另外, u 的父级 当 p 存在时, 删除连接 u 和 将其放在 p 的边, 作为 p 从 l 的父级进行连接。
    3. l 给右边的孩子 如果 r 存在,则 连接它,使其成为 l 和 将其放在 r 的边, 作为 r 从 u 的左子级。 作为
    4. u 从 l 的右子节点进行连接。
  • 二分探索木 T 中包含的节点 u 的左旋转执行如下。这个操作 当 u 没有右子节点时,无法执行此操作。

    1. u 的右孩子 r 。 删除连接
    2. u 和 将其放在 r 的边。另外, u 的父级 当 p 存在时, 删除连接 u 和 将其放在 p 的边, 作为 p 从 r 的父级进行连接。
    3. r 到左孩子 l 存在,则 连接它,使其成为 r 和 将其放在 l 的边, 作为 l 从 u 的右子节点进行连接。
    4. u 从 r 的左子级。 作为

入力

输入将以以下形式通过标准输入给出。

Q
t_1 v_1
.
.
.
t_Q v_Q
  • 1 在第几行 1 一个整数,表示行中的查询数。 Q (1≦Q≦400,000) 。 来自行
  • 继续 Q 行之后 行 i 在行 i th 查询类型和表示节点值的整数 保证不存在于 t_i, v_i(1≦t_i≦4,1≦v_i≦400,000) 用空格分隔。
  • 種類 1 查询中,值为 一个节点使得 v 是 保证不存在于 T 中。 保证存在于
  • 種類 2,3,4 查询中,值为 一个节点使得 v 是 保证不存在于 T 中。

出力

按给定顺序排列的每个查询的结果 1 输出每一行。要输出,请使用以下命令 请注意,它属于 3 类型。 查询

  1. 種類 2 如果
  2. 種類 3 查询中,值为 一个节点使得 v 一个节点使得 u 没有左孩子 如果
  3. 種類 4 查询中,值为 一个节点使得 v 一个节点使得 u 没有右孩子 如果正确答案是满足

部分点

针对此问题设置了部分分数。

  • 1≦Q≦1,000 的数据集 如果对满足 20 分被给予。
  • 1≦t_i≦2(1≦i≦Q) 的数据集给出正确答案,除了上述部分点外, 30 分被给予。
  • 如果答案对于没有附加约束的数据集是正确的,则进一步 100 获得的总积分 获得 150 点。 从第

入力例 1

13
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
2 1
2 2
2 4
2 6
2 7

出力例 1

0
0
-1
-1
-1
  • 1 起 在高达 8 的查询中 根据查询中给出的顺序将节点插入到 T 中。请注意,插入期间不会执行旋转操作。
  • 下图中 第 8 次查询后 表示 T 。
  • 节点内部写入的值表示该节点具有的值,节点旁边写入的值表示以该节点为根的子树的高度。
  • 通过给定的查询 T 的形状保证是唯一的。 在第
  • 9 个查询中,值为 1 节点左子树的高度使得 h(lst) 和右子树的高度 h(rst) 都是 0 所以 在第 h(lst)-h(rst)是 0 。
  • 10 个查询中, h(lst) 和 将其放在 h(rst) 都是 1 所以 在第 h(lst)-h(rst)是 0 。
  • 11 个查询中, h(lst) 是 2 、 h(rst) 是 3 所以 在第 h(lst)-h(rst)是 -1 。
  • 12 个查询中, h(lst) 是 1 、 h(rst) 是 2 所以 在第 h(lst)-h(rst)是 -1 。
  • 13 个查询中, h(lst) 是 0 、 h(rst) 是 1 所以 在第 h(lst)-h(rst)是 -1 。
  • 没有子树的子树的高度是 请注意 0 。
  • 这个情况是 2 满足两个部分点约束的两个部分点约束。 在第

図 1 : 8 个查询结束时 T 在第


入力例 2

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
3 4
2 2
2 4
2 6
2 7
3 7

出力例 2

-3
-2
-1
-1
-1
  • 下图中 第 9 个查询执行右旋转之前, T 向左,旋转后 右侧显示 T 。
  • 请注意节点之间位置关系的变化。 在第
  • 14 个查询中,值为 节点不存在满足 7 的左子节点,因此-1。 由于它不满足
  • 通过给定的查询 T 的形状保证是唯一的。 在第
  • 这个情况是 1 满足第二部分点约束。 通过第

図 2 : 9 次查询 T 的转变 在第


入力例 3

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
4 6
2 2
2 4
2 6
2 7
4 6

出力例 3

0
-1
1
1
-1
  • 下图中 第 9 个查询执行左旋转之前, 节点不存在满足 T 向左,旋转后 右侧显示 T 。
  • 请注意节点之间位置关系的变化。 在第
  • 14 个查询中,值为 节点不存在满足 6 的右子节点,因此-1。 由于它不满足
  • 通过给定的查询 T 的形状保证是唯一的。 在第
  • 这个情况是 1 满足第二部分点约束。 通过第

図 3 : 9 次查询 T 的转变 在第