P3721 [AH2017/HNOI2017]单旋

    • 239通过
    • 776提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 Link-Cut Tree,LCT Splay 模拟 离散化 线段树 各省省选 2017 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    H国是一个热爱写代码的国家,那里的人们很小去学校学习写各种各样的数据结构。伸展树(splay)是一种数据结构,因为代码好写,功能多,效率高,掌握这种数据结构成为了H国的必修技能。有一天,邪恶的“卡”带着他的邪恶的“常数”来企图毁灭H国。“卡”给H国的人洗脑说,splay如果写成单旋的,将会更快。“卡”称“单旋splay”为“spaly”。虽说他说的很没道理,但还是有H国的人相信了,小H就是其中之一,spaly马上成为他的信仰。而H国的国王,自然不允许这样的风气蔓延,国王构造了一组数据,数据由m(不超过10^5)个操作构成,他知道这样的数据肯定打垮spaly,但是国王还有很多很多其他的事情要做,所以统计每个操作

    所需要的实际代价的任务就交给你啦。数据中的操作分为5种:

    1. 插入操作:向当前非空spaly中插入一个关键码为key的新孤立节点。插入方法为,先让key和根比较,如果key比根小,则往左子树走,否则往右子树走,如此反复,直到某个时刻,key比当前子树根x小,而x的左子树为空,那就让key成为x的左孩子;或者key比当前子树根x大,而x的右子树为空,那就让key成为x的右孩子。该操作的代价为:插入后,key的深度。特别地,若树为空,则直接让新节点成为一个单个节点的树。(各节点关键码互不相等。对于“深度”的解释见末尾对spaly的描述。)

    2. 单旋最小值:将spaly中关键码最小的元素xmin单旋到根。操作代价为:单旋前xmin的深度。(对于单旋操作的解释见末尾对spaly的描述。)

    3. 单旋最大值:将spaly中关键码最大的元素xmax单旋到根。操作代价为:单旋前xmax的深度。

    4. 单旋删除最小值:先执行2号操作,然后把根删除。由于2号操作之后,根没有左子树,所以直接切断根和右子树的联系即可。(具体见样例解释)。操作代价同2号操作。

    5. 单旋删除最大值:先执行3号操作,然后把根删除。操作代价同3号操作。

    对于不是H国的人,你可能需要了解一些spaly的知识,才能完成国王的任务:

    1. spaly是一棵二叉树,满足对于任意一个节点x,它如果有左孩子lx,那么lx的关键码小于x的关键码。如果有右孩子rx,那么rx的关键码大于x的关键码。

    2. 一个节点在spaly的深度定义为:从根节点到该节点的路径上一共有多少个节点(包括自己)。

    3. 单旋操作是对于一棵树上的节点x来说的。一开始,设f为x在树上的父亲。如果x为f的左孩子,那么执行zig(x)操作(如上图中,左边的树经过zig(x)变为了右边的树),否则执行zag(x)操作(在上图中,将右边的树经过zag(f)就变成了左边的树)。每当执行一次zig(x)或者zag(x),x的深度减小1,如此反复,直到x为根。总之,单旋x就是通过反复执行zig和zag将x变为根。

    输入输出格式

    输入格式:

    输入文件名为 splay.in。

    第一行单独一个正整数 m (1 <= m <= 10^5)。

    接下来 m 行,每行描述一个操作:首先是一个操作编号 c( 1<=c<=5),既问题描述中给出的 5 种操作中的编号,若 c= 1,则再输入一个非负整数 key,表示新插入节点的关键码。

    输出格式:

    输出文件名为 splay.out。

    输出共 m 行,每行一个整数,第 i 行对应第 i 个输入的操作的代价。

    输入输出样例

    输入样例#1: 复制
    5
    1 2
    1 1
    1 3
    4 
    5
    输出样例#1: 复制
    1 
    2 
    2
    2 
    2

    说明

    20%的数据满足: 1 <= m <= 1000。

    另外 30%的数据满足: 不存在 4,5 操作。

    100%的数据满足: 1<=m<=10^5; 1<=key<=10^9。 所有出现的关键码互不相同。 任何一个非插入操作,一定保证树非空。 在未执行任何操作之前,树为空。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。