神仙题，我会把我自己思考的过程一步步写出来。
初看这题时感觉没什么思路，所以随便算了点东西。很容易发现如果对于一个 $i$，$q_i\geq q_{i+1}$，那么 $q_i$ 就没有意义，每次把元素放进来时先把头部比它大的都弹走，再把它放进去，设处理完的 size 为 cnt。
然后就是这道题的精髓所在了！很容易就可以发现 $q_i+1$ 的串是 $q_i$ 串的弱循环。所以就可以弄一个 solve 函数，solve (x, y) 意思是处理第 $q$ 个串循环 $y$ 遍的贡献。运行 solve (cnt, 1) 就可以了，但是 solve 函数怎么设计呢？
以下设 $q_i=len_i$
前面的循环节可以用 solve (cnt - 1, len[cnt] / len[cnt - 1]) 处理，但是后面多余的呢？
这时我们发现需要改变 solve 函数了，设 solve (x, y) 为处理前 $x$ 个字符循环 $y$ 次的贡献。
转移首先要找到第一个 $t$，使得 $len[t] < x$，前面的部分仍然是循环，solve (len[t], x / len[t]) 就解决了，后面还有 $x$ $\bmod$ $len[t]$ 个剩余的，这些只循环 1 次，solve (x % len[t], 1) 就可以了。
另外，注意下边界问题，如果 $x\leq n$ 了，那么前 $x$ 个字符就是 $1\cdots x$，这些的出现次数都 $+1$，用差分维护就行。
分析一下时间复杂度，$T(x)= x + T(x - 1) + T (\frac{x}{2})=x^2$，考虑优化。
时间主要用在了 $x$ 和 $T(x-1)$ 上，第一个用二分可以 $\log_n$。关于第二个，solve 函数都是 solve (len[t], x / len[t]) 的形式，第一个参数也就 $n$ 种。因此，我们用一个桶 $f$，$f[t]$ 统计的是 solve 第一个参数为 $len[t]$ 时，$y$ 的和。最后再把 f 中的一起统计一下就行。
现在的 solve 函数就成了这样：
void solve (int x, int y) { if (x <= n) { d[1] += y; d[x + 1] -= y; return; } int t = lower_bound (len + 1, len + cnt + 1, x) - len - 1; f[t] += x / a[t] * y; solve (x % a[t], y); }
结束后，我们倒序循环一下。$f[i]$ 拆成 $f[i - 1] * \lfloor\frac{len[i]}{len[i - 1]}\rfloor + len[i] $ $\bmod$ $len[i - 1]$，前面的加到 $f[i-1]$ 上，后面的继续用 solve 函数。（即 solve (len[i] % len[i - 1], f[i]) ）。
此题的 $q_i$ 也可能小于 $n$，所以遇到这种情况，我们把 $n$ 设为最小的 $q_i$，输出时 $>n$ 的输出 $0$ 即可。
这样，时间复杂度降到了 $n\log^2 n$，另外注意开长整型和特判 $q=0$ 的情况。
少量注释的代码：
#include <iostream> #include <algorithm> #define int long long using namespace std; int n, q, cnt; int a[100005], d[100005], f[100005]; void solve (int x, int y) {//求解前 x 个字符的贡献乘上 y if (x <= n) { d[1] += y; d[x + 1] -= y; return; } int t = lower_bound (a + 1, a + cnt + 1, x) - a - 1; f[t] += x / a[t] * y;//其实是前 a[t] 个字符乘上 x / a[t] 加上剩余的。 solve (x % a[t], y); } signed main () { int x, z; cin >> n >> q; if (q == 0) { for (int i = 1; i <= n; i ++) cout << 1 << "\n"; return 0; } z = n; a[++ cnt] = n; for (int i = 1; i <= q; i ++) { cin >> x; n = min (n, x); while (cnt != 0 && a[cnt] >= x) -- cnt; a[++ cnt] = x; } solve (x, 1); for (int i = cnt; i >= 2; i --) { f[i - 1] += a[i] / a[i - 1] * f[i]; solve (a[i] % a[i - 1], f[i]); } d[1] += f[1]; d[n + 1] -= f[1]; for (int i = 1; i <= n; i ++) { d[i] += d[i - 1]; cout << d[i] << "\n"; } for (int i = n + 1; i <= z; i ++) cout << 0 << "\n"; return 0; }