一部分技巧同时优化了复杂度。

0. 字符集仅为 $9$，请不要在 SAM 中开大小为 $26$ 的 nxt 数组。
1. 矩阵乘法要写压位的 $O(k^2)$ 版本。为了获得更小的常数，请将 if 判断换成位运算筛选以去除分支。
2. 写 zkw 线段树。
3. （优化效果最显著）注意到线段树上单点修改的是一段区间，而本题中 pushup 代价很大，所以我们将一次询问中需要修改的位置先都找出来，然后逐层修改。这样可以避免一个点被 pushup 好几次。
4. 使用快读快写。

经过笔者的测试，使用上述所有技巧后，最慢点用时仅为 1.85s。