#17936. Splay树

Splay树

题目背景

这一天,出题人 five_rice_water 在出题的时候看到了这样一个神奇的数据结构,并且想要用这个东西出一道题为难一下大家。

题目背景

Splay 的定义如下。

splay tree,中文名伸展树。

其是一种自平衡二叉排序树,通过其特有的splay操作,可以使得整棵树在维持二叉排序树性质的情况下,又不至于退化为链。

splay树支持对数据进行查询、插入、删除等操作,且各操作的时间复杂度摊还后皆是 ,是一种相对高效的数据结构。

Splay树并不在乎二叉排序树是否时刻平衡,而是通过在每次操作时进行微调来使得树趋于平衡。

每当我们对二叉排序树进行一次操作(查询、插入、删除等)时,我们就将操作的节点通过旋转操作挪到根节点上,并且使得整棵树依旧满足二叉排序树的性质,这一系列过程我们称之为splay操作。

splay操作不单单是将操作节点挪到根节点,还将从原根节点到操作节点路径上的所有节点都进行了一次优化,使得其深度缩减,通过这一方法来使得二叉排序树不至于退化为链。

此时 five_rice_water 突发奇想,希望你能根据以上定义,解决一下这个问题:

  • 给你两个整数 a,ba,b, 输出 a+ba+b 的值。

输入格式

一行两个整数 a,ba,b

输出格式

一行一个整数 a+ba+b

2 3
5

数据范围

对于 100%100\% 的数据,保证 1a,b10181\le a,b \le 10^{18}