题解：AT_agc003_e [AGC003E] Sequential operations on Sequence

jltyzy · 2026-11-13 15:05:04 · 题解

对于两个相邻的操作，如果后一个更小，它会把前面的部分截断，上一个操作就没有用了。这样不断消去，最终操作序列严格递增，可以用单调栈维护，计入 b 数组，初始把 n 作为第一个操作。

考虑从后向前累计每个操作区间在最后用了多少次，设为 cnt_i，最初 cnt_m=1。当前操作用到的上一个操作的完整部分为 cnt_i\lfloor\frac{b_i}{b_{i-1}}\rfloor，累加到 cnt_{i-1} 中。

设剩余部分 r 为 b_i\bmod b_{i-1}，它也可以拆分成更小的操作的几块完整部分和剩余部分，我们直接二分到最后一个 b_{pos}\le r 的操作，做同样的累加。重复此过程，直到 r=0 或 r<b_1，这样对第一个操作额外开一个差分数组记录，最后将差分数组前缀和与 cnt_1 相加。

因为取模每次至少减半只有 \log 次，再加上二分，复杂度 O(q\log q\log V)。

#include <bits/stdc++.h>
using namespace std;
long long a[100005],b[100005],d[100005],cnt[100005],len;
int main()
{
    int q;
    scanf("%lld%d",&a[0],&q);
    for(int i=1;i<=q;i++)
        scanf("%lld",&a[i]);
    stack <int> stk;
    for(int i=0;i<=q;i++)
    {
        while(!stk.empty()&&a[i]<=a[stk.top()])
            stk.pop();
        stk.push(i);
    }
    int len=stk.size();
    for(int i=len;i>0;i--)
    {
        b[i]=a[stk.top()];
        stk.pop();
    }
    cnt[len]=1;
    for(int i=len;i>1;i--)
    {
        cnt[i-1]+=cnt[i]*(b[i]/b[i-1]);
        long long r=b[i]%b[i-1];
        while(r!=0)
        {
            int pos=upper_bound(b+1,b+len+1,r)-b-1;
            if(pos==0)
            {
                d[1]+=cnt[i];
                d[r+1]-=cnt[i];
                break;
            }
            cnt[pos]+=cnt[i]*(r/b[pos]);
            r%=b[pos];
        }
    }
    for(int i=1;i<=b[1];i++)
    {
        d[i]+=d[i-1];
        printf("%lld\n",cnt[1]+d[i]);
    }
    for(int i=b[1]+1;i<=a[0];i++)
        puts("0");
    return 0;
}