对于T4，显然可以记录 $pre_i$ 为以 $i$ 为右端点，最短合法子串的左端点，再减 $1$

则先设 $pre_i=i-1$ ,若 $a_{pre_i}\neq a_i$，则不断设 $pre_i=pre_{pre_i}$，直到 $pre_i=0$

同时记录 $f_i$ 为以 $i$ 为右端点的合法子串数量，则有 $f_i=f_{pre_i}+1$（如果 $pre_i$ 存在的话） ，答案就是 $f_i$ 求和

这样时间复杂度是 $O(n\Sigma)$ 的，其中 $\Sigma$ 是字符种类，这样复杂度对于 T4 是正确的

然而对于 CF1223F $\Sigma=3e5$ ，这时直接做会超时，观察大数据会发现问题出在即使 $[0,pre_i]$ 中没有 $a_i$ 了，还在往前跳，则考虑记录 $first_i$ 表示 $a_i$ 最早出现的位置，当 $pre_i<first_i$ 时，直接设 $pre_i=0$

这样我们就可以愉快的 AC 啦！/xk