前言
笑点解析，赛时代码有三行，其中有三个非常离谱的错误。然而，这样的东西可以通过到大样例 6，并使得无法测试剩余两个大样例，只好假装自己过了。最后喜提 0 昏。
思路
考虑第二问，发现找到这样的区间看起来十分困难，故考虑用第一问的答案减去 l,r 不合法的区间。
故需要计算任意前缀和后缀的答案。先观察一下性质，发现如果 [l,r] 是好的，则 [l,r-1] 也一定是好的。故确定左端点后右端点可行的位置是从 l 开始的一个区间，记这个右端点为 p_l。那么，对于拼接的第二个字符串，就是在 (l,r+1] 内 p_i 最大的一个，依次类推。
则从 i 向这个最大的位置连边，在 k-1 步之内到达的所有 u 的 p_i 都减一，i 加一算一个前缀和即可得到对于所有 r 合法的 l,k 的个数。需要注意如果出现了自环要特判。
现在只需要求对于所有 l 合法的 r,k 个数即可。发现 i 从那个最大的位置可以转移得到当前位置每种不同的 r 的最小的 k 的个数。而这之间的变化是全局平移 1、单点修改。查询是一段长度为 k 的区间，可以使用可持久化线段树通过。