[JSOI2008] 火星人

gold_bread · 2023-08-25 11:16:02 · 个人记录

题意：给出一个字符串，支持三种操作

1.求两个后缀的lcp

2.修改某个位置上的字符

3.在某个位置插入一个字符

查询次数q \leq 10^4 ，字符串总长L \leq 10^5 ,操作数m \leq 1.5*10^5

感觉大多是平衡树做法，这里提供一种定期重构做法

设每B次操作后重构出前缀hash值的数组，另建立一个a数组，存放一个块内修改的位置

2，3操作时，直接将修改/插入放到a数组内，可能会有一些位移，不是很复杂，注意，我们还要使a数组有序，那么每次类似于插入排序一下

这样复杂度就是O(mB+q*logL*B+m/B*L)

取B=sqrt(L)即可达到最小复杂度O(msqrt(L)+q*logL*sqrt(L))

代码细节比较多