[??记录]AT2005 [AGC003E] Sequential operations on Sequence
command_block
2021-01-25 13:18:54
**题意** : 维护序列 $A$ ，初始为 $\{1,2,...,m\}$。
现在给出 $q$ 个操作，每次操作把数组长度变为 $n_i$，若要新增数，则将数组重复。
问所有操作完成后 $1\sim n$ 各出现了多少次。
$m,q\leq 10^5,n_i\leq 10^{18}$ ，时限$\texttt{2s}$。
------------
好题。
不难发现，若相邻的两次操作 $n_i,n_{i+1}$ 满足 $n_i>n_{n+i}$ ，则前者是无用的。
由此，只需要保留所有后缀最小值，这可以将操作化简成一个单调不降的序列。
先考虑如何求最终序列单个位置的值，不难发现只要依次模 $n_i$ 就好了。
而有定理 $n\geq m\Rightarrow n\bmod m\leq n/2$ ，所以模 $n/2$ 次就变成 $0$ 了。
再考虑整个序列，设 $A_i$ 为第 $i$ 次操作后的序列，则有 :
$A_i=\lfloor n_i/n_{i-1}\rfloor A_{i-1}+A_{i-1}[1,n_{i}\bmod n_{i-1}]$。
前者是子问题，对于后者，只需要二分出最后一个 $n_j\leq n_{i}\bmod n_{i-1}$ ，然后就也是子问题了。
每个 $i$ 会产生一个侧边的分支，侧边的分支经过 $O(\log n)$ 轮后就会消失。
正着做时需要随机访问之前的版本，并不方便，考虑倒着做，而为每个版本记下贡献次数。
注意，若最后子问题变为了原数组的前缀，则需要给 $cnt$ 数组前缀加，差分即可。
复杂度为 $O(n\log^2n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
int m,sq,q;
ll sn[MaxN],n[MaxN],o[MaxN],c[MaxN];
void calc(ll l,ll w)
{
int t=upper_bound(n+1,n+q+1,l)-n-1;
if (t==0){c[l]+=w;return ;}
o[t]+=w*(l/n[t]);
calc(l%n[t],w);
}
int main()
{
scanf("%lld%d",&m,&sq);sn[0]=m;
for (int i=1;i<=sq;i++)scanf("%lld",&sn[i]);
ll sufx=sn[sq]+1;
for (int i=sq;i>=0;i--)
if (sn[i]<sufx)
n[++q]=sufx=sn[i];
reverse(n+1,n+q+1);
o[q]=1;
for (int i=q;i>1;i--){
o[i-1]+=o[i]*(n[i]/n[i-1]);
calc(n[i]%n[i-1],o[i]);
}
for (int i=m;i;i--)c[i]+=c[i+1];
for (int i=1;i<=m;i++)
printf("%lld\n",(i<=n[1])*o[1]+c[i]);
return 0;
}
```