线段树维护等差数列

题面

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=2e5+10;
const int mod=3*5*7*11*13*17*19*23;
const int inv_2=mod-mod/2;
int n;
int a[maxn];
int q,op,x,y,z,v;

struct seg{
    #define ls cur<<1
    #define rs cur<<1|1

    int sum[maxn<<2],lx[maxn<<2],ld[maxn<<2];
    void pushup( int cur )
    {
        sum[cur]=(1ll*sum[ls]+sum[rs])%mod;
    }
    void pushdown( int cur,int l,int r )
    {
        if( lx[cur] || ld[cur] )
        {
            int mid=l+r>>1;
            sum[ls]=(1ll*sum[ls]+cal(l,mid,lx[cur],ld[cur]) )%mod;
            lx[ls]=(1ll*lx[ls]+lx[cur])%mod;
            ld[ls]=(1ll*ld[ls]+ld[cur])%mod;

            lx[cur]=( 1ll*lx[cur]+1ll*(mid+1-l)*ld[cur]%mod )%mod;

            sum[rs]=(1ll*sum[rs]+cal(mid+1,r,lx[cur],ld[cur]) )%mod;
            lx[rs]=(1ll*lx[rs]+lx[cur])%mod;
            ld[rs]=(1ll*ld[rs]+ld[cur])%mod;

            lx[cur]=ld[cur]=0;
        } 
    }

    int cal( int l,int r,int val,int d )
    {
        int cnt=r-l+1;
        int res=(1ll*val+(1ll*val+1ll*(cnt-1)*d%mod)%mod )%mod;
        res=1ll*res*cnt%mod*inv_2%mod;
        return res;
    }

    void build( int cur, int l,int r )
    {
        sum[cur]=lx[cur]=ld[cur]=0;
        if( l==r )
        {
            sum[cur]=a[l]%mod;
            return;
        }
        int mid=(l+r)>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(cur);
    }

    void update( int cur,int l,int r,int L,int R ,int val,int d )
    {
        if( L<=l && r<=R )
        {
            sum[cur]=(1ll*sum[cur]+cal(l,r,val,d) )%mod;
            lx[cur]=(1ll*lx[cur]+val)%mod;
            ld[cur]=(1ll*ld[cur]+d)%mod;
            return;
        }
        pushdown(cur,l,r);
        int mid=l+r>>1;

        if( mid>=R ) update(ls,l,mid,L,R,val,d);
        else if( mid<L ) update(rs,mid+1,r,L,R,val,d);
        else
        {
            update(ls,l,mid,L,mid,val,d);
            val=(1ll*val+1ll*(mid+1-L)*d%mod)%mod;
            update(rs,mid+1,r,mid+1,R,val,d);
        }

        pushup(cur);
    }

    int query( int cur,int l,int r,int L,int R )
    {
        if( L<=l && r<=R ) return sum[cur];
        int mid=l+r>>1;
        int res=0;
        pushdown(cur,l,r);
        if( L<=mid ) res=(1ll*res+query(ls,l,mid,L,R) )%mod;
        if( R>mid ) res=(1ll*res+query(rs,mid+1,r,L,R) )%mod;
        return res;
    }

}tree;


int main()
{
    scanf("%d",&n);
    for( int i=1;i<=n;i++ ) scanf("%d",&a[i]);
    tree.build(1,1,n);
    scanf("%d",&q);
    while( q-- )
    {
        int op;
        scanf("%d",&op);
        if( op==1 )
        {
            int L,R,val,d;
            scanf("%d%d%d%d",&L,&R,&val,&d);
            tree.update(1,1,n,L,R,val,d);
        }
        else
        {
            int L,R,m;
            scanf("%d%d%d",&L,&R,&m);
            int ans=tree.query(1,1,n,L,R);
            printf("%d\n",ans%m);
        }
    }
    return 0;
}
/*
4
1 1 1 1
5
1 1 2 1 1
2 1 2 100
2 1 1 100
*/