Type: Default 1000ms 256MiB

Splay树

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

这一天,出题人 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}

平行赛(参加者AK不了提头来见)

Not Attended
Status
Done
Rule
Ledo
Problem
12
Start at
2025-7-10 18:30
End at
2025-7-10 20:30
Duration
2 hour(s)
Host
Partic.
26