Treap

\(\text{Treap}\)是一种通过维护堆和二叉搜索树两重性质来限制树高的平衡树。

每一个节点都被赋予了两个值,称作\(val\)和\(key\),分别按照BST和堆的性质维护:

  • 小根堆:每一个节点的\(key\)都小于等于他的两个子节点的\(key\)
  • 二叉树:每一个节点的\(key\)都比他左子的\(val\)大,比右子的\(val\)小

每一个节点的\(key\)是随机指定的,这样可以保证期望树高为\(\log n\)

继续阅读“Treap”

后缀自动机与线性构造后缀树——转自fanhq666(fhq范爷)

转自范爷的blog:http://fanhq666.blog.163.com/blog/static/8194342620123352232937/
原始文件:https://blog.edgaru089.ml/custom-items/后缀自动机与线性构造后缀树.txt

冬令营上我犯了最大的一个错误,就是在陈立杰讲后缀自动机的时候睡觉。
这导致了,我在冬令营之后只能花费好几个不眠之夜来思考后缀自动机到底是什么。
突然,在某天的梦里,我看到了一幅神奇的图景,我突然发现,一切都是那么的明晰了。

继续阅读“后缀自动机与线性构造后缀树——转自fanhq666(fhq范爷)”

洛谷P4911 河童重工的计算机

题面见 https://www.luogu.org/problemnew/show/P4911

作为出题人,我有责任写一篇题解(逃

这题的初衷就是一个庞大的大模拟,刚刚见到未来程序改这道题有着一种自然的熟悉感呢(笑)

但是不像那道题,这道题没有什么语义树之类的高深的东西呢,只有对代码能力的考察,像我这种初中三年荒废在搞项目的人,代码功底还可以说是十分扎实的呢(笑)

继续阅读“洛谷P4911 河童重工的计算机”