可以算是平衡树的半个版题吧。
做法是维护节点表示字符串的hash，询问的时候二分长度。
可以维护hash是因为BKDR-HASH的计算方法是
$$BKDR(s)=\sum_{i=1}^{n}S_ip^{n-i}$$
向上合并的时候左面儿子的hash乘上$p^{k+1}$，加上节点权值乘上$p^{k}$，加上右儿子的hash即为此节点的hash值，其中$k$为右儿子大小。
这道题做的时候我把字符串直接串成一个长链，接到平衡树上面（以前都是这么写的），虽然很low但是能过
。然后后来我发现了网上大家都是像线段树那么构建的，我好方。so sad
时间复杂度$O(n \log^2 n)$
照例https://github.com/cjsoft/noip/tree/master/after_lnoi/d0527
这两天效率好低