题目大意:

P3373（线段树模板）
如题，已知一个数列，你需要进行下面三种操作：
1、将某区间每一个数乘上 xx
2、将某区间每一个数加上 xx
3、求出某区间每一个数的和

思路:

记录维护区间乘法已经取模的线段树模板

AC Code:

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL MAXN=1e6+10;
LL a[MAXN],mod;
struct node{
    LL l,r;
    long long sum;
    long long lazy;
    long long lazyc;
}Tree[MAXN<<2];
inline LL ls(LL p){ return p<<1;}//左儿子
inline LL rs(LL p){ return p<<1|1;}
void PushUP(LL p)//向上更新
{
    Tree[p].sum=(Tree[ls(p)].sum+Tree[rs(p)].sum)%mod;
    Tree[p].sum%=mod;
}
void build(LL p,LL l,LL r)
{
    Tree[p].lazy=0;
    Tree[p].lazyc=1;
    Tree[p].l=l;Tree[p].r=r;
    if(l==r) {Tree[p].sum=a[l];return;}
    LL mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    PushUP(p);
}
void PushDown(LL p,LL l,LL r)//lazy节点下移
{
    if(Tree[p].lazy)
    {
        LL len=(r-l+1);
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod+Tree[p].lazy%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod+Tree[p].lazy%mod)%mod;
 
        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod+Tree[p].lazy%mod*(len-(len>>1)))%mod;
 
        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod+Tree[p].lazy%mod*(len>>1))%mod;
 
        Tree[p].lazy=0;//下移后，原节点取消标记
    }
}
void PushDownc(LL p,LL l,LL r)
{
    if(Tree[p].lazyc!=1)//数据中有可能有负数，
    {
        Tree[ls(p)].lazyc=(Tree[ls(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazyc=(Tree[rs(p)].lazyc%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].lazy=(Tree[ls(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].lazy=(Tree[rs(p)].lazy%mod*Tree[p].lazyc%mod)%mod;
        Tree[ls(p)].sum=(Tree[ls(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[rs(p)].sum=(Tree[rs(p)].sum%mod*Tree[p].lazyc%mod)%mod;
        Tree[p].lazyc=1;
    }
    PushDown(p,l,r);
}
void UpDate(LL L,LL R,LL c,LL l,LL r,LL p)//更新操作
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazy=(Tree[p].lazy%mod+c)%mod;
        Tree[p].sum=(Tree[p].sum%mod+c*(r-l+1))%mod;
        return;
    }
    PushDownc(p,l,r);//加法的更新操作也应当使得乘法的lazyc标记向下移动
    LL mid=(l+r)>>1;
    if(mid>=L) UpDate(L,R,c,l,mid,ls(p));
    if(mid<R) UpDate(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
void Updatec(LL L,LL R,LL c,LL l,LL r,LL p)
{
    if(l>=L&&r<=R)//这个区间完全在更新区间的内部
    {
        Tree[p].lazyc=(Tree[p].lazyc%mod*c)%mod;
        Tree[p].lazy=(Tree[p].lazy%mod*c)%mod;
        Tree[p].sum=(Tree[p].sum%mod*c)%mod;
 
        return;
    }
    PushDownc(p,l,r);
    LL mid=(l+r)>>1;
    if(mid>=L) Updatec(L,R,c,l,mid,ls(p));
    if(mid<R) Updatec(L,R,c,mid+1,r,rs(p));
    PushUP(p);
}
LL query(LL L,LL R,LL l,LL r,LL p)
{
    LL res=0;
    if(l>=L&&r<=R) return Tree[p].sum%mod;
    LL mid=(l+r)>>1;
 
    PushDownc(p,l,r);
 
    if(mid>=L) res+=(query(L,R,l,mid,ls(p))%mod);
    if(mid<R) res+=(query(L,R,mid+1,r,rs(p))%mod);
    return res%mod;
}
int main()
{
    LL n,m;
    scanf("%lld%lld%lld",&n,&m,&mod);
    for (LL i = 1; i <=n ; ++i) {
        scanf("%lld",&a[i]);
    }
    build(1,1,n);
    while (m--)
    {
        LL flag;
        scanf("%lld",&flag);
        if(flag==1)
        {
            LL x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            Updatec(x,y,z%mod,1,n,1);
        }
        else if(flag==2)
        {
            LL x,y,z;
            scanf("%lld%lld%lld",&x,&y,&z);
            UpDate(x,y,z,1,n,1);
        }
        else if(flag==3)
        {
            LL x,y;
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(x,y,1,n,1)%mod);
        }
    }
    return 0;
}