题解：AT_arc077_d [ARC077F] SS

提供一种数据结构维护的做法。

考虑一次变换是在干什么。手玩样例可以发现，分两种情况：

第一种情况是简单的，直接去计算即可。

下面讨论第二种情况，手玩样例，考虑其每次变换长度的增加量。记 $f^0(S)=S$。设 $d_i=|f^i(S)|-|f^{i-1}(S)|$。对于 $i\ge 3$，有 $d_i=d_{i-2}+d_{i-1}$。

先用字符串哈希算出 $d_1$ 和 $d_2$。

用平衡树维护变换。每次操作相当于将字符串其中一段取出，并接在其后面。具体地，我们取出平衡树包含的 $O(dep)$ 个区间，然后像替罪羊树那样，将这些区间重构成一棵树。构造新树，直接将原来的树定为新树的左子树，区间重构树定为新树的右子树。

重构树时，需要信息重用。就像主席树那样，将重构树的最下面的区间直接指向原树的对应区间。

平衡树需要记录区间长度，以及当前区间下每种小写字母出现的次数。注意取出平衡树包含的 $O(dep)$ 个区间时，区间中点不是 $\frac{l+r}2$，而是 $l+lth_{ls}-1$。

最后将 $[l,r]$ 区间的答案算一下即可。

考虑复杂度。每次取出区间为 $O(dep)$ 个，新树深度最多会增加 $O(\log dep)$。一开始为 $O(\log |S|)$ 的深度。深度增加量的增加量较小，所以复杂度为 $O(c(\log |S|)^2)$。$c$ 表示变换的次数，为 $O(\log _{\frac{\sqrt 5+1}2} r)$。所以总时间复杂度为 $O(|S|+(\log _{\frac{\sqrt 5+1}2} r) (\log |S|)^2)$。

代码。