T1
首先有"本质不同的回文串的数量级是 (O(n)) 的"
证明很简单，考虑sam上最多有 (2n-1) 个节点，同时这些节点中每个最多有一个回文串
（如果有多个的话，那么短串的 (endpos) 比长串要多）
其实在这个题目里面关注的是 (midpos)，那么给所有的回文串标号
(manacher) 处理所有的回文中心，把短串向长串连边得到一个树
对于每次处理的 (id[i-r[i]+1,i+r[i]-1]) 异或上 (i) 最后按照 (SAM) 维护 (endpos) 个数那样维护 (midpos) 的异或和即可
一开始想的是倍增后缀树的做法，其实和正解是一致的，考完了之后优化了一下思路写了出来
所以以后要注意的是难题口胡完了要写
复杂度 (Theta(n))
注意的几个点：
(1.) 手写 (hash)
(2.) 字符串清空一定要手动清全，因为 (t[i]) 后面的遗留可能对计算造成影响
(3.) 森林的根节点的 (res[x]) 不能取最大值
T2
子串排名递减，总和增加，所以两者交点最多有一个，二分统计即可
但是考试的时候不会如何求排名，所以 (SAM) 维护子串排名方式如下：
每个后缀树上的点维护的是一个后缀，那么我们翻转之后就能得到前缀
先算 (endpos) 大小表示这个点一共多少个串
然后把所有的出边都标号，标号就是 (s[pos[x]+len[fa[x]]])
这样每个点在后缀树上排序之后再 (dfs) 得到每个点的 (rk)
对于每个 ([l,r]) 倍增出来对应的点之后直接 (rk[now]+len[now]-(r-l+1)+1) 即可
T3
后缀自动机板子题，不过考试的过程中发现 (dfs) 会本地爆栈，浪费了很多时间回忆如何写基数排序，如下：
for(reg int i=1;i<=tot;++i) ton[len[i]]++;
for(reg int i=1;i<=slen;++i) ton[i]+=ton[i-1];
for(reg int i=tot;i>=1;--i) id[ton[len[i]]--]=i;
for(reg int i=tot;i>=1;--i){
if(sz[id[i]]>1) ans=max(ans,1ll*sz[id[i]]*len[id[i]]);
sz[fa[id[i]]]+=sz[id[i]];
} printf("%lld
",ans);
端正态度，加速思考