[AGC003E] Sequential operations on Sequence

题意

给定一个整数序列，有 \(q\) 次操作，每次操作从无限复制的序列里面选择前 \(q_i\) 个元素作为当前的序列。

问 \(1\) 到 \(n\) 每个整数在最终序列中出现的次数。

\(n \le 10 ^ 5, q_i \le 10 ^ {18}\)

Sol

想象一下每次操作，都是复制若干次前一次的序列然后拼上一段余数组成的。

考虑倒推，每次往前乘上一个系数，但是这样还是没法做，因为需要设一个双元组 \((x, y)\) 表示第 \(i\) 次操作的前 \(y\) 个的贡献，记忆化后依然至少是 \(n ^ 2\) 的。

考虑冗余的操作以及计算，注意到事实上若 \(i < j\) 且 \(s_i > s_j\) 那么 \(i\) 一定不会有贡献，换句话说对于操作序列维护一个单调栈，最终栈内的元素才能产生贡献。

回到之前的做法，发现其实第一维没有用！每次我们只需要找到操作序列里第一个大于等于她的位置就行了，因为中间一段的操作对她都没有贡献。

注意到每次操作是模一个数字，也就是对于每个操作与上一个操作的余数，这个层数显然不会超过 \(\log\)，因此状态数是 \(O(n \log n)\) 的，递归里需要塞一个 \(\texttt{upper_bound}\)，最终复杂度为 \(O(n \log ^ 2 n)\)。