莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 这题需要两个懒标记，一个加法，一个乘法
2. 加法与乘法同时操作（先乘后加）：(x * a + b) * c + d = x * a * c + b * c + d
3. 其他部分就是线段树带有懒标记的基本操作

可参考： 一个简单的整数问题2

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 100010;

int n,p,m;
int a[N];
struct Node
{
    int l,r;
    int sum;
    int add; //加法的懒标记
    int mul; //乘法的懒标记
}tr[N*4];

//由子节点求父节点
void pushup(int u)
{
    tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)%p;
}

//(x * a + b) * c + d = x * a * c + b * c + d
void eval(Node &t,int add,int mul)
{
    t.sum=((LL)t.sum*mul+(LL)(t.r-t.l+1)*add)%p;
    t.add=((LL)t.add*mul+add)%p;
    t.mul=(LL)t.mul*mul%p;
}

void pushdown(int u)
{
    eval(tr[u<<1],tr[u].add,tr[u].mul);
    eval(tr[u<<1|1],tr[u].add,tr[u].mul);

    //将懒标记清空
    tr[u].add=0,tr[u].mul=1;
}

//初始化线段树
void build(int u,int l,int r)
{
    if(l==r) tr[u]={l,r,a[l],0,1};
    else 
    {
        tr[u]={l,r,0,0,1};

        int mid=l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);

        pushup(u);
    }
}

//修改操作
void modify(int u,int l,int r,int add,int mul)
{
    if(tr[u].l>=l&&tr[u].r<=r) eval(tr[u],add,mul);
    else 
    {
        pushdown(u);

        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1,l,r,add,mul);
        if(r>mid) modify(u<<1|1,l,r,add,mul);

        pushup(u);
    }
}

//查询操作
int query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;

    pushdown(u);

    int mid=tr[u].l+tr[u].r>>1,sum=0;
    if(l<=mid) sum=query(u<<1,l,r);
    if(r>mid) sum=(sum+query(u<<1|1,l,r))%p;

    return sum;
}

int main()
{
    cin>>n>>p;

    for(int i=1;i<=n;i++) cin>>a[i];

    //建立线段树
    build(1,1,n);

    cin>>m;

    int t,l,r,d;
    while(m--)
    {
        cin>>t>>l>>r;

        //乘法操作
        if(t==1)
        {
            cin>>d;
            modify(1,l,r,0,d);
        }
        //加法操作
        else if(t==2)
        {
            cin>>d;
            modify(1,l,r,d,1);
        }
        //查询操作
        else cout<<query(1,l,r)<<endl;
    }

    return 0;
}