线段树——维护序列（两个懒标记的情况）

传送门：维护序列

思路：这道题和一个简单的整数问题那道题2相比只是在原本的假发懒标记的基础上加多了一个乘法的懒标记，但这里的懒标记是有优先级问题的当两个懒标记或多个懒标记堆积在一起的时候先乘再加和先加再乘的结果是不一样的。

所以本题的唯一难点就是在如何处理懒标记上。

解决：

对于一个要标记的节点p,分为以下几种情况：

在已经有一个加法懒标记和一个乘法懒标记的基础上加多一个乘法的懒标记

对于区间内的每一个数x都有

（x*mul+add）*mul1;

可以转化为x*mul*mul1+add*mul 

在已经有一个加法懒标记和一个乘法懒标记的基础上加多一个加法的懒标记

（x*mul+add+add1） 这里add可以直接加上新的add1

代码拿出来就是:

void eva(tree &t,int add,int mul)
{
    t.sum=((ll)t.sum*mul+(ll)(t.r-t.l+1)*add)%mod;
    t.mul=((ll)t.mul*mul)%mod;
    t.add=((ll)t.add*mul+add)%mod;
}

因为新懒标记不会同时到来，只能一个一个传递，所以上面的函数中的每一次调用add为0要么mul为1;

所以这条式子起作用的时候mul是等于1的。

t.add=((ll)t.add*mul+add)%mod;

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10;
struct tree
{
    int l, r;
    ll sum,add,mul;
}t[N<<2];
ll a[N];
int n,m,mod;
void pushup(int p)
{
    t[p].sum=(t[2*p].sum+t[2*p+1].sum)%mod;
}
void eva(tree &t,int add,int mul)
{
    t.sum=((ll)t.sum*mul+(ll)(t.r-t.l+1)*add)%mod;
    t.mul=((ll)t.mul*mul)%mod;
    t.add=((ll)t.add*mul+add)%mod; //这里为什么是乘mul呢？
}
void pushdown(int p)
{
    eva(t[p*2],t[p].add,t[p].mul);
    eva(t[p*2+1],t[p].add,t[p].mul);
    t[p].add=0;
    t[p].mul=1;
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    t[p].mul=1;
    if(l==r) {t[p].sum=a[l];return ;}
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
     pushup(p);
}
void change (int p,int l,int r,int add,int mul)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        eva(t[p],add,mul);
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change(2*p,l,r,add,mul);
    if(r>mid) change(2*p+1,l,r,add,mul);
      pushup(p);
}
ll ask(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    pushdown(p);
    int mid=(t[p].r+t[p].l)>>1;
    ll sum=0;
    if(l<=mid) sum=ask(2*p,l,r);
    if(r>mid) sum=(sum+ask(2*p+1,l,r))%mod;
    return sum;
}
int main()
{
    scanf("%d%d",&n,&mod);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);
    scanf("%d",&m);
    while(m--)
    {
        int l,r,d,t;
    scanf("%d%d%d",&t,&l,&r);
    if(t==1)
    {
        scanf("%d",&d);
        change(1,l,r,0,d);
    }else if(t==2)
    {
        scanf("%d",&d);
        change(1,l,r,d,1);
    }else
       printf("%lld\n",ask(1,l,r));
    }
    return 0;
}