[BZOJ2105 增强型LCP]【Unaccept】【Splay+hash & 二分答案】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=2105

【题目大意】

给定一个串，你可以对它进行修改插入删除等操作。

然后有一种询问操作，LCP(i,j)表示求S[i..n]和S[j..n]的最长公共前缀。

总操作数<=10^5

但是各种修改字符串的操作总数<=5000

10^5-5000=95000，几乎全是询问操作。。。

【算法分析】

众所周知、判断字符串是否相等可以利用hash来达到很高的正确率。

然后经过询问某牛，无符号整数爆了相当于Mod。有符号之间爆好像是未定义什么的。于是一般都是用无符号整数。

然后既然是相当于Mod，所以利用* + -的hash函数对于一个相同的字符串，无论计算的次序如何都是会相等的。

于是简单地把hash值定为S[1]*p^n+S[2]*p^(n-1)+S[3]*p^(n-2)….

p就随便取个素数什么的。比如13、131~

然后对于求LCP，有一个二分答案然后判断是否相同的想法。

那么，我们需要快速知道某个区间的hash值。

区间问题、比较经典的有ST表和线段树这种。

1、ST表，因为每次修改都要重建，所以我把这个想法抹杀了，实际上本题是CQF《New Lcp》里面的原题。就是利用ST表的思想。而且确实每次修改以后都以O(n)的复杂度重建。。。当然他论文后面还有个利用平衡常数的常数优化。

2、由于本题长短会变，所以用平衡树取代线段树。然后现在相当于维护一个线性表。所以Splay是比较好的选择。另外区间的处理上Splay也比较方便。

【结果】

一看题目就想到第二种算法。敲出来以后干脆地TLE了。

每次修改的时间复杂度是O(lg n)

每次询问的时间复杂度是O(lg^2 n)

本题的特殊性在于询问很多，修改很少。

而ST表的时间复杂度

修改O(n)

询问O(lg n)

然后我这沙茶就悲剧了= =。

其实如果把修改弄多一点，我觉得我这个算法还是理论上不错的。就是常数比较大。

【CODE】

Splay+hash=TLE

经对拍，该代码无误。当然hash本身是有概率出错的。

 http://xiudaima.appspot.com/code/detail/4405003