题目翻译

题解

译者的话：

后缀自动机

题目：

说明：

S是用到的数组，S0~S3代表四个阶段

系数向量是a

第0轮（Rader变换后）：

第1轮：

第2轮：

第3轮：

后记：

其实本来我是想写个类似讲解的东西的……然后发现智商太低写不出来……然后就像这样弄了个演示……然后就发现它变成了公式恐惧症患者的福音(╯‵□′)╯︵┻━┻

然而！这并没有什么卵用(╯‵□′)╯︵┻━┻

不过这里按照Rader-Brenner算法（也就是刘汝佳的模板所采用算法）详细地写出来了N=8的FFT变换的全过程，可能对理解FFT有一定帮助吧……

[……]

继续阅读

题目翻译：

题解翻译：

这道题中的摩天大楼描述了被称作跳跃表（Skip List）的数据结构。跳跃表在某种意义上和AVL、红黑树相似，因为它支持O(logN)的插入，操作和查找（包括上下界查询），同时支持常数时间的在排序顺序中前后移动。跳跃表和任何树结构都不同，因为它有实用的，不需要线程锁的（所谓‘无锁’），线程安全的实现方式。无锁跳跃表被用作MemSQL中主要的存储数据结构，并且Bob使用的，穿过摩天大楼的算法是一种O(logN)的方法，它能让人们估算跳跃表的大小。因此，如果Bob最[……]

继续阅读