LargeDumpling

我只负责打字,内容我也不知道从何而来。

LYDSY 3224 Tyvj 1728 普通平衡树

传送门

        感觉此题题面描述较坑,有很多东西没写出来。先给出由HugeGun实现的Datamaker的代码。

vector做法

        不知为何此题可用vector过掉,O2优化真是强啊。

        就当熟悉一下STL的用法好了,STL一直是我的短板Drz。

        reserve是什么用还是隐约不太懂。

Treap做法

        此题的标解应该就是平衡树呢。

        Treap是一类B(inary)S(earch)T(ree),相比朴素的二叉搜索树,其结点保存了一个优先级v,并通过旋转保证父节点的v大于子结点的v,即使v保持大根堆的性质。这样二叉搜索树的期望复杂度就应该是log(n)级别,进而降低了各种操作的时间复杂度。

        实现过程中,删除操作容易出错,应当小心。查询前缀和后缀本可以通过查询排名和查询k大联合起来实现,但这里给出了一种常数较小的做法。


        目前仅会以上两种做法,还有一种速度特快的离线方法,使用Fenwick Tree实现,需要先将数据离散化。

评论

© LargeDumpling | Powered by LOFTER