bzoj1798

题解：

同洛谷2023

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

ll p,v,sum_,addv[N],mulv[N],sumv[N],a[N];

int n,m,c,x,y;

void pushdown(int o,int l,int l1,int r,int r1)

{

    sumv[o*]=(sumv[o*]*mulv[o]+addv[o]*(l1-l+))%p;

    sumv[o*+]=(sumv[o*+]*mulv[o]+addv[o]*(r1-r+))%p;

    addv[o*]=(addv[o*]*mulv[o]+addv[o])%p;

    addv[o*+]=(addv[o*+]*mulv[o]+addv[o])%p;

    mulv[o*]=(mulv[o*]*mulv[o])%p;

    mulv[o*+]=(mulv[o*+]*mulv[o])%p;

    mulv[o]=;

    addv[o]=;

}

void updatemul(int o,int l,int r)

{

    if(x<=l&&r<=y)

     {

        mulv[o]=(mulv[o]*v)%p;

        addv[o]=(addv[o]*v)%p;

        sumv[o]=(sumv[o]*v)%p;

        return ;

     }

    int mid=(l+r)>>;

    pushdown(o,l,mid,mid+,r);

    if(x<=mid)updatemul(o*,l,mid);

    if(y>mid)updatemul(o*+,mid+,r);

    sumv[o]=(sumv[o*]+sumv[o*+])%p;

}

void updateadd(int o,int l,int r)

{

    if(x<=l&&r<=y)

     {

        addv[o]=(addv[o]+v)%p;

        sumv[o]=(sumv[o]+v*(r-l+))%p;

        return ;

     }

    int mid=(l+r)>>;

    pushdown(o,l,mid,mid+,r);

    if(x<=mid)updateadd(o*,l,mid);

    if(y>mid)updateadd(o*+,mid+,r);

    sumv[o]=(sumv[o*]+sumv[o*+])%p;

}

void create(int o,int l,int r)

{

    addv[o]=;

    mulv[o]=;

    if(l==r)

     {

        sumv[o]=a[l];

        return ;

     }

    int mid=(l+r)>>;

    create(o*,l,mid);

    create(o*+,mid+,r);

    sumv[o]=(sumv[o*]+sumv[o*+])%p;

}

void query(int o,int l,int r)

{

    if(x<=l&&r<=y)

     {

        sum_+=sumv[o]%p;

        sum_%=p;

        return ;

     }

    int mid=(l+r)>>;

    pushdown(o,l,mid,mid+,r);

    if(x<=mid)query(o*,l,mid);

    if(y>mid)query(o*+,mid+,r);

    sumv[o]=(sumv[o*]+sumv[o*+])%p;

}

int main()

{

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++)scanf("%lld",&a[i]);

    create(,,n);

    scanf("%d",&m);

    while (m--)

     {

        scanf("%d%d%d",&c,&x,&y);

        if(c==)

         {

            scanf("%d",&v);

            updatemul(,,n);

         }

        if(c==)

         {

            scanf("%d",&v);

            updateadd(,,n);

         }

        if(c==)

         {

            sum_=;

            query(,,n);

            printf("%lld\n",sum_);

         }

     }

    return ;

}