BZOJ3682: Phorni 后缀平衡树+线段树

题解：

终于会写后缀平衡树了0.0

首先我们要知道Treap是什么东西。Treap是一种二叉平衡树，同时是重量平衡树，也即单次插入删除期望最大影响的子树大小为$O(logn)$。

也就是说，我们可以暴力重新计算该子树的信息而不用担心复杂度爆炸。

考虑利用重量平衡树来处理动态顺序维护问题。

现在有一个序列，你可以在序列中的某个位置插入一个元素，询问就是询问两个元素的先后顺序。

直接利用平衡树可以做到插入、询问均为$O(logn)$。

考虑动态标号法，在平衡树中的每个节点都记录$[l,r]$，这个节点的值为$\lfloor\frac{l+r}{2}\rfloor$。

如比较两个元素的顺序，只需要比较两个平衡树节点的值就行了，于是是$O(1)$。

现在要插入一个元素，在旋转之后树的形态可能会发生变化，好在最大影响的子树大小为$O(logn)$，所以直接暴力计算子树内的节点的值就行了，于是单次插入复杂度依然为$O(logn)$。

由于重量平衡树深度期望为$O(logn)$，所以需要的权值的值域在long long范围就可以保证完全区分了。

后缀平衡树就是维护后缀之间字典序从小到大的有序序列的平衡树。

假如对于字符串$S[1,n]$，已经构造好$S'[i,n]$的后缀平衡树，考虑如何构造$S''[i-1,n]$的后缀平衡树。

那么只需插入后缀$i-1$就行了。

那么在平衡树中进行插入时，就需要比较两个后缀的字典序大小咯。

而我们可以做到$O(1)$，原因在：若两个后缀首字母相同，则同时去掉首字母，转化为已经存在在平衡树中的两个后缀的顺序问题，利用动态标号就能做到$O(1)$询问；如果首字母不同则显然$O(1)$完成。

维护后缀平衡树实质上就是一个动态顺序维护问题，因此可以做到$O(nlogn)$构造，$O(1)$询问两个后缀的字典序大小，并支持在串的开头插入一个字符。

关于平衡树复杂度的证明有时间再说。

代码：