AGC003E Sequential operations on Sequence

题意 : 维护序列 ，初始为 。

现在给出 个操作，每次操作把数组长度变为 ，若要新增数，则将数组重复。

问所有操作完成后 各出现了多少次。

，，时限 。

---

好题。

不难发现，若相邻的两次操作 满足 ，则前者是无用的。

由此，只需要保留所有后缀最小值，这可以将操作化简成一个单调不降的序列。

先考虑如何求最终序列单个位置的值，不难发现只要依次模 就好了。

而有定理 ，所以模 次就变成 了。

再考虑整个序列，设 为第 次操作后的序列，则有：

前者是子问题，对于后者，只需要二分出最后一个 ，然后就也是子问题了。

每个 会产生一个侧边的分支，侧边的分支经过 轮后就会消失。

正着做时需要随机访问之前的版本，并不方便，考虑倒着做，而为每个版本记下贡献次数。

注意，若最后子问题变为了原数组的前缀，则需要给 数组前缀加，差分即可。

复杂度为 。