AGC003E题解

· · 题解

首先要筛去无用操作，这我为啥想不到嘞 /kel 。

如果 a[i]\geq a[i+1] ，那么 a[i] 肯定没有用，所以一开始我们拿 a 跑个单调栈。

然后考虑扩展的结果，就是把上一次的结果复制几遍然后再加上一些边角料。

边角料很难做啊，先考虑没有边角料该是什么情况，我们就把复制次数乘起来，得到 a[1] 总共被复制了多少次就做完了。

正着做怎么都处理不了这个边角料，我们考虑反着拆解。

我们的最终目标是把拆解成一大堆形如 1\cdots x 的段来统计答案，这样的段只有 O(Q) 种，其中又可以细分为 a[1] 和其它复制过程中产生的边角料。

我们不需要一步到位，于是我们从后往前枚举当前最大的模式串 a[i] ，把 a[i] 的复制次数分配到更小的 a[j] 和其它的边角料上面去。

考虑拆解后 a[i] 会变成什么样子，肯定是 \{a[p[1]],a[p[2]],\cdots,a[p[t]],tail\} （tail是一段边角料），其中这个序列单调不增，我们递归实现这个过程，每次把当前剩余串拿出来，找到被它包含的最长子模式串 a[j] ，用 a[j] 分解 tmp ，计算给 a[j] 的贡献再递归下去。最终只剩下一块边角料前缀了，直接贡献给最终答案。

这么做一次的复杂度是 O(\log n) 的，因为每次我们都会把 len(tmp) 对一个比它小的值取模，这样至少会让 len(tmp) 减半。

所以我们就在这个过程中记录模式串 a[i] 当前接到的贡献次数 F[i] 就好了，最终就全部贡献要么被预先加上去了，要么存在了 F[1] 里面。