题解：CF438D The Child and Sequence

题目

• Codeforces
• Luogu

---

思路

题目要求我们完成三种操作：

• 区间求和
• 区间取模
• 单点修改

1，3两种都非常简单，问题在于如何维护区间取模。

可以想到维护区间最大值，如果小于模数则不处理，否则将这个区间重新pushup。

如何证明该复杂度？注意到，一个数最多会被取模 $log{a_i}$ 次，所以复杂度我 $O(nlog_nlog{\max{a_i}})$ 。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int N=1e5+5;

ll n,m;
ll a[N];

struct segtree
{
    struct node
    {
        ll sum,mx;
    } tr[N*4];

    void pushup(ll p)
    {
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
        tr[p].mx=max(tr[p<<1].mx,tr[p<<1|1].mx);
    }

    void build(ll p,ll l,ll r)
    {
        if(l==r)
        {
            tr[p]={a[l],a[l]};
            return ;
        }

        ll mid=l+r>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
    }

    void update(ll p,ll l,ll r,ll x,ll y)
    {
        if(l==r)
        {
            tr[p]={y,y};
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid)
        {
            update(p<<1,l,mid,x,y);
        }
        else
        {
            update(p<<1|1,mid+1,r,x,y);
        }

        pushup(p);
    }


    void update_mod(ll p,ll l,ll r,ll x,ll y,ll v)
    {
        if(l==r)
        {
            tr[p].sum%=v;
            tr[p].mx%=v;
            return ;
        }

        ll mid=l+r>>1;
        if(x<=mid&&tr[p<<1].mx>=v)
        {
            update_mod(p<<1,l,mid,x,y,v);
        }
        if(y>mid&&tr[p<<1|1].mx>=v)
        {
            update_mod(p<<1|1,mid+1,r,x,y,v);
        }

        pushup(p);
    }


    ll query(ll p,ll l,ll r,ll x,ll y)
    {
        if(x<=l&&y>=r)
        {
            return tr[p].sum;
        }

        ll mid=l+r>>1;
        ll ret=0;
        if(x<=mid)
        {
            ret+=query(p<<1,l,mid,x,y);
        }
        if(y>mid)
        {
            ret+=query(p<<1|1,mid+1,r,x,y);
        }

        return ret;
    }
} T;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>m;
    for(ll i=1;i<=n;i++)
    {
        cin>>a[i];
    }

    T.build(1,1,n);

    while(m--)
    {
        ll typ,l,r;
        cin>>typ>>l>>r;
        if(typ==1)
        {
            cout<<T.query(1,1,n,l,r)<<"\n";
        }
        else if(typ==2)
        {
            ll x;
            cin>>x;
            T.update_mod(1,1,n,l,r,x);
        }
        else
        {
            T.update(1,1,n,l,r);
        }
    }

    return 0;
}

---

然而没有什么技巧。