题解：AT_arc077_d [ARC077F] SS

· · 题解

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

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

  1. 如果 S 的最短前后缀等于 \frac{|S|}2，那么每次变换等价与将 S 变为 SS。
  2. 如果 S 的最短前后缀小于 \frac{|S|}2，设最短前后缀长度为 d，那么变换等价于将 S 的 [d+1,|S|-d] 部分复制并添加在 S 的后面。

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

下面讨论第二种情况，手玩样例，考虑其每次变换长度的增加量。记 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)。

代码。