最后还是看了题解。
首先用单调栈把操作序列变成单调递增的（证明去掉一个相邻逆序对中的大数不会对答案产生影响）。
后面的内容想出来是几天之后了……
我描述不太清楚， 这里仅给出大体思路：
题目的目标就是要维护一个答案数组 ( t ans[i])， 其中 ( t ans[i]) 表示所有操作操作完之后 ( t i) 的数量 。
为了表达清楚那么一点点，现在在这里定义两种与序列相关的运算（设有一数列 ( t q)）：
- 数乘， ( t k*q, kinBbb N_+) ，表示将 ( t q) 复制 ( t k) 次拼接起来
- 答案数组加上数列 ( t q)， ( t ans += q)， 表示对于 ( t forall iin[1,|q|])， 让 ( t ans[q_i]) 加上 ( t 1)
设操作总数为 ( t Q)， 设第 ( t i) 次操作后的数列为 ( t S_i)。
那么题目要求的就是要进行 ( t ans += S_Q) 之后输出整个 ( t ans) 数组。
显然， ( t S_i) 可以被分解为若干段 ( t S_{i-1}) 和一段 ( t S_imod S_{i-1}) （描述不精确， 感性理解下）
那么 ( t ans += S_i) 就相当于先后进行 ( t ans += lfloorfrac{|S_i|}{|S_{i-1}|} floor*S_{i-1})， ( t ans += S_imod S_{i-1}) 。
注意到这个 ( t ans += S_imod S_{i-1}) 的操作也是可以像刚才那样分解， 套一个二分， 分解完只需要 ( t O(log^2)) 的时间。
整个算法的总体思路就是把 “给答案数组加上一个较晚的数列” 不断拆成 “给答案数组加上若干个不一定相同的较早的数列”。
//A了， 函数内参数没开longlong
#include<bits/stdc++.h>
using namespace std;
const int MN = 100003;
int n,q,tp;
long long a[MN];
long long times[MN], ans[MN];
void divide(long long len, long long timeS) { // 把给 “ans数组加上第 id 次操作后的序列的长度为 len 的前缀 timeS 次” 分解
int j = upper_bound(a+1,a+tp+1,len) - a - 1;
if(!j) ans[1]+=timeS, ans[len+1]-=timeS;
else {
times[j] += (len/a[j]) * timeS;
divide(len%a[j], timeS);
}
}
int main() {
scanf("%d%d", &n,&q);
a[++tp] = (long long)n;
for(int i=1;i<=q;++i) {
long long x;
scanf("%lld",&x);
while(tp && a[tp]>=x) --tp;
a[++tp] = x;
}
times[tp] = 1ll; //题目就是要求把 ans 数组加上一个最终数列
for(int i=tp;i>1;--i) {
times[i-1] += (a[i]/a[i-1])*times[i]; //分解前面的整段
divide(a[i]%a[i-1],times[i]);
}
ans[1] += times[1];
ans[a[1]+1] -= times[1];
for(int i=2;i<=n;++i) ans[i] += ans[i-1];
for(int i=1;i<=n;++i) cout << ans[i] << '
';
return 0;
}