[AGC003E]Sequential operations on Sequence

本文主要是介绍[AGC003E]Sequential operations on Sequence，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Sequential operations on Sequence

题解

~~其实还是蛮有趣的。~~

首先，我们发现，我们最后保留下来的，会对我们产生意义的数组操作的长度，一定是递增的。
因为一次减少操作，相当于只给我们保留下来上次操作的一个前缀，相当于上次操作没有增长那么长。
所以我们可以先用一个单调栈维护哪些操作，这样就只剩下增加的操作了。

接下来，我们考虑我们的答案该怎么计算。
显然最开始，我们是一个长度为 $q_n$ 的前缀，出现了一次，由于我们每次是循环式出现，所以我们可以将长度为 $q_n$ 的前缀分解成两部分，一部分是上一个操作的重复出现，一个是一个单独的前缀。
我们发现，对于一个任意长度的前缀，我们都有着类似的分解方式。
譬如一个长度为 $y$ 的前缀，如果比它小的最长的操作的长度为 $x$ ，那么我们可以将其分解成 $\lfloor\frac{y}{x}\rfloor$ 个长度为 $x$ 的前缀，与 $1$ 个长度为 $x\%y$ 的前缀。
我们发现分解成的前缀中， $x$ 是我们一个操作的长度，我们可以把它当成一个已经出现过的长度，而我们的 $x\%y$ 虽然是新出现的，但它显然是小于我们 $y$ 一半的长度的，所以这样的新增对于一个起点来说，在一条不经过某一个操作长度的路径上，是不会超过 $\log\,y$ 次。
我们总共有 $m$ 个操作长度，也就是说，我们不同长度的数量是不会超过 $m\log n$ ，事实上这个上界是极松的，这也就意味着我们可以暴力对每个长度的贡献进行转移。

当一个点转移到小于最短操作长度的位置后，也就意味着它已经贡献到了一个从 $1$ 开始的连续前缀，我们可以先加上一个差分值，最后再后缀和统计答案。
由于我们每次的转移都一定会转移到一个比当前长度小的数，从大到小枚举每个长度进行转移。
枚举的长度虽然是不连续的，但随便找个STL或数据结构就能够很方便的维护了，具体可见代码。

时间复杂度 $O\left(Q\log n\log(Q\log n)\right)$ 。

源码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 5000005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
typedef pair<int,int> pii;
const double INF=1e9;
const int mo=1e9+7;
const int mod=1e5+3;
const int inv2=5e8+4;
const int jzm=2333;
const int zero=2000;
const int n1=1000;
const int lim=100000;
const int orG=3,ivG=332748118;
const long double Pi=acos(-1.0);
const double eps=1e-12;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int Q,stak;LL n,sta[MAXN],ans[MAXN],dp[MAXM];
priority_queue<LL>q;bool vis[MAXM];
struct HashMap{LL val[MAXM];int head[MAXN],tot,nxt[MAXM];int query(LL x){int pos=x%mod,now=head[pos];while(now&&val[now]!=x)now=nxt[now];if(!now)now=++tot,nxt[now]=head[pos],head[pos]=now,val[now]=x;return now;}
}Mp;
signed main(){read(n);read(Q);sta[++stak]=n;for(int i=1;i<=Q;i++){LL x;read(x);while(stak&&x<=sta[stak])stak--;sta[++stak]=x;}int st=Mp.query(sta[stak]),x=stak;dp[st]=1;q.push(sta[stak]);vis[st]=1;while(!q.empty()){LL t=q.top();q.pop();int p=Mp.query(t);if(t<=sta[1]){ans[t]+=dp[p];continue;}while(x&&sta[x]>=t)x--;LL ty=sta[x],tz=t%sta[x];int y=Mp.query(ty);dp[y]+=dp[p]*(t/ty);if(!vis[y])q.push(ty),vis[y]=1;int z=Mp.query(tz);dp[z]+=dp[p];if(!vis[z])q.push(tz),vis[z]=1;}for(int i=sta[1];i>0;i--)ans[i]+=ans[i+1];for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);return 0;
}