自闭集训 Day3
字符串
SAM
考虑后缀树。
SAM的parent树是反串的后缀树，所以后面加一个字符的时候相当于往串前面加一个字符，恰好多出了一个后缀。
于是可以以此来理解SAM。
每一条路径对应原串的一个子串。
每一个终止节点对应一些后缀。
所有到同一个点的路径对应的子串互为后缀，长度连续。
parent树是反串的后缀树。
SAM可以用来构造SA。（？？？）
回文树
一个串的本质不同的回文子串的个数是\(O(n)\)的。
每个点只表示一个回文串。
SAM和回文树的复杂度都是均摊的，所以不能可持久化。
BZOJ 4556
SAM上线段树合并裸题，直接二分长度然后可以知道\(endpos\)必须在\([a+len-1,b]\)里面，倍增找一下什么的就没了。
NOI2016 十连测 D5T2
我们知道\(per_i=i-next_i\)，所以容易想到把KMP可持久化，然而由于KMP复杂度均摊，所以如果直接搞你人就没了。
我们定义一个数组\(trans_{x,c}\)表示在\(x\)后面新加一个\(c\)那么\(next\)会指到哪里。设\(s_{next_x+1}=c'\)，那么分两种情况。如果\(c\ne c'\)，那么\(trans_{x,c}=trans_{next_x,c}\)，否则\(trans_x=next_x+1\)。
于是我们发现\(trans_x\)只会从\(trans_{next_x}\)改一个过来，于是可以可持久化线段树把复杂度搞到严格\(\log n\)，于是就没了。
另一种方法：考虑\(next_x\)，如果\(next<x/2\)那么可以放心跳，只会跳\(\log n\)次。否则，我们发现前\(x\)位有循环节。如果\(c\)等于对应的那一位那么就做完了，否则无论如何也不可能匹配上，就可以直接模\(x-next_x\)。
BZOJ4310
简单题。直接在后缀数组上二分rank最大的后缀的长度，然后变成了有一堆线段，要撒一些点把这些线段切开，贪心即可。
Fim1
发现\(T_x\)必须是\(S\)的子串，否则询问毫无意义。
于是我们可以直接对\(S\)建SAM，然后后面加字符就是跳\(ch\)，前面就是跳\(parent\)树，询问就线段树合并然后乱搞即可。
区间本质不同子串
离线，固定右端点。
维护序列\(ans_l\)表示固定当前右端点的时候左端点为\(l\)答案多少。
右端点往右一格，会多出很多后缀，相当于SAM上节点到根的一条链又出现了一遍。
每个节点记录\(tag_x\)， 表示上一次出现的位置在哪里。
那么这一次做出的贡献就是\(ans[tag_x-len+1,r-len+1]++\)。
还要注意由于每个节点代表的是一堆后缀，所以其实有某些段加的不是定值，而是关于下标的一个一次函数。
右移完之后，这一段的\(tag\)就搞成一样的了。
注意到这个东西很像LCT的access操作，可以直接暴力做，用线段树维护。
于是总复杂度\(O(n\log^2 n)\)。
区间本质不同回文串
类比上面的方法，仍然设\(ans_l\)和\(tag_x\)，但这次用回文树做。
然而，这次回文树的节点表示的回文串长度不连续，就比较恶心了。
但是我们知道：在一个点结束的回文串的起始位置组成了\(\log n\)个等差数列。
为什么？考虑最长的那个回文串，其他回文串显然都是他的border。
有一个关于border集合的定理：它们组成\(\log n\)个等差数列。
于是我们就得到了这个结论。
然后我就不会了，不知道怎么就做到\(O(n\sqrt{n})\)了。
咕了
update：菜鸡pb来修锅了……
熟悉回文树的人（显然不包括我）肯定可以看出来，这\(O(\log n)\)个等差数列是很容易拆出来的。
考虑只有一个等差数列的时候，新加入一个\(r\)会发生什么。对于某一个\(l\)，如果他包含了某一个回文串，那么比这个串更短的串都不会更新\(l\)的答案了，因为对称一下之后就已经出现过了。
所以我们看一下最长的那个串上一次在哪里出现，然后所有原来不包含那个串的\(l\)答案都是加1。
有多个等差数列呢？显然包含了这一段某一个串之后更短的串都不会有贡献，所以可以分开考虑。
上一次出现的位置可以查询回文树上的子树得到。
复杂度\(O(n\log^2 n)\)。
CF700E
又是一道做过然后又忘掉了的一题。/kk
见博客。
某题
动态往一个串后面加字符，加完之后询问任意两个前缀的最长回文后缀长度。
回文自动机，lcp就是树上的lca深度。每次向后扩展一位就求一下与之前节点的lca的深度之和，用LCT维护。
回文树、回文自动机没有学好，要注意。
某题
求
\[
\sum_{a,b\in s} [|a|+|b|-2lcp(a,b)<L]
\]
我tm这都没看出就是两点距离真是没救了，我退役算了……
发现每个点代表的距离是一段区间，所以如果点分治的话会比较麻烦。然而，如果上边分治，那么这题就没了。
Deep Purple
见博客。
NOI赛前集训 D6T2
做过啦……然而还是不会……
首先发现设\(dp_x\)表示从\(x\)开始走升上天堂的概率，那么我们应该先选\(dp_x\)大的。
考虑每次转移都是除以二，所以用二进制保存，就变成了一个trie。
要排序，就是要给trie做一个SA。
数据范围太大，不能带log，考虑后缀自动机转后缀数组。
用某种方法建出后缀数组（咕了）之后就可以统计信息，还要FFT来优化。
复杂度\(O(n+K\log^2 L)\)。
Lyndon串
对于字符串\(S\)，如果\(S\)的最小后缀是他本身，那么\(S\)就是Lyndon串。
这也等价于\(S\)是他循环移位中最小的一个。
如果\(u,v\)是Lyndon串，那么\(uv\)是Lyndon串当且仅当\(u<v\)。
Lyndon分解：任意串\(v\)可以被唯一分解成一堆Lyndon串连在一起，而且这些串单调递减。
存在性显然，而唯一性：假设从第\(i\)个开始不同，设\(|s_i|<|s'_i|\)，然后……已经会证，但不太好说明。
Duval算法，\(O(n)\)搞出Lyndon分解：已经会了。
NOI赛前集训 D6T3
做过啦，会啦……