【暴力】AGC003 Sequential operations on Sequence

分析：

我写的暴力居然过了。。奇迹啊。。。

直接从后往前依次询问，对最后一次询问，询问其前$a_q$个位置，然后转移到$q?1$位置，就变为前$a_{q?1},a_q\%a_{q?1}$位置……

但这个是$n^2$的啊。。加了一个小优化：每次从最大的一个开始，然后依次判断到小于等于$a_i$为止。

然后就过了。。。感觉数据是不是太弱啊。。。话是这么说但我自己也没找到能卡这方法的数据。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
typedef map<ll,ll>::iterator mit;
int n,q;
ll qx[MAXN];
map<ll,ll> mp;
ll used[MAXN];
int main(){
    SF("%d%d",&n,&q);for(int i=1;i<=q;i++)SF("%lld",&qx[i]);qx[0]=n;mp[qx[q]]++;for(int i=q-1;i>=0;i--){
    while(mp.rbegin()->first>qx[i]){
    mit it=mp.end();it--;	mp[it->first%qx[i]]+=it->second;mp[qx[i]]+=it->second*(it->first/qx[i]);mp.erase(it);}}mit it=mp.begin();for(;it!=mp.end();it++)used[it->first]+=it->second;for(int i=n;i>=1;i--)used[i]=used[i]+used[i+1];for(int i=1;i<=n;i++)PF("%lld\n",used[i]);
}