T1

申必题，后面再做

算了先做吧

看来要高精度

先二进制拆分，然后递归输出

毕竟最后要输出，所以输出长度应该是有保障的

直接做即可

草了byd是大模拟

写了一个小时

希望能过

T2

SA板子题？

好像又不太对

感觉不如t1

这么大的询问一眼离线

建trie树，每个点此时表示一个子串

每个点额外维护一个 tim 表示子串最近加入时间

从左往右添加即可

对于区间加操作则差分

注意子串长度

对于一个点 $i$ ，他表示的子串长度为 $len_i$ ,时间为 $tim_i$ ，那么其左端点为 $tim_i-len_i+1$ ,新左端点为 $r-len_i+1$ ，那么对应的操作就是区间 $[tim_i-len_i+2,r-len_i+1]$ 加1

应该就做完了？

T3

不会，不会是字符串专场吧

欸

眼熟

草了，开猜

对于任意两个前缀 $S_1,S_1c$ 而言，$S_1$ 作为前缀且接上一个以 $c$ 为开头的后缀能够表示出来的字符串一定是 $S_1c$ 作前缀的子集

也就是说：$S_1+c$ 其实是无用的，不需要统计

但假设没有任意一个前缀满足 $S_1+z$ ，那么他就是唯一的

所以建两棵trie树， 排除掉其有儿子的情况后接上其他的即可

可能是对的？

建议跑跑对拍

等下

这个后缀不太对劲

它的开头有点问题

我的第一步其实本质上是在去重，即去掉相同前缀

第二步也需要去重，不过去的是后缀的重

但事实上而言，我是不是直接哈希也是可行的？

所以前面的去重，后面的哈希

可能会漏记

我们额外规定 “对于一个前缀树上的节点，若它的上层节点能够通过添加一个字符而变为它自身，那么就算合法”

其实本质上而言，我们是在对能够表示出来的字符串做分类

如果一个字符串 $S$ 能够被表示为 $S_1S_2$ 那么他一定能够表示为一个唯一的 $S_1S_2$ 匹配满足 $S_1$ 最长，$S_2$ 不为0

T4

矩阵乘法？