BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash 字符串 数据结构

BZOJ1014 [JSOI2008]火星人prefix 无旋Treap+Hash

题意就是给出字符串,动态插入、修改字符。我们需要数据结构,动态维护序列的哈希值。 $$H(l,r)=\sum _{i=l} ^{r} S[i]*base^{i-l}$$ 考虑这个计算一段字符串hash值的公式,可以通过维护子树hash值,再利用Treap的分裂合并操作动态维护,最后二分答案就好啦。 ···