P4036 [JSOI2008]火星人 （平衡树，字符串哈希）

· · 个人记录

看到题目以为是奇怪的待修改SA，然而并没有想到怎么修改。

正解：

看到有插入操作，就可以想平衡树了。

然后两个后缀的 LCP 不仅可以用后缀数组，还可以用万能的 哈希 。

于是就在平衡树上维护一段区间的哈希值，具体的push_up方法长这样：

hs[x]=hs[lc]*pw[sz[rc]+1]+val[x]*pw[sz[rc]]+hs[rc];

然后这道题就做完了。

然而，因为我平衡树写得太拉，插入操作乱写，导致调了两个多小时.......

这是错误代码：

Find(x);//意思是把x旋上来了后，直接把新节点跟x和x的右儿子连边了...
val[++newp]=c-'a'+1;
ch[newp][0]=rt,ch[newp][1]=ch[rt][1];
fa[rt]=fa[ch[rt][1]]=newp,ch[rt][1]=0;
Push_Up(rt),rt=newp,Push_Up(rt);