[Ahoi2009]Seq 维护序列seq(线段树既有乘又有加的LAZY操作)

传送门

题意：给出一个线段，对这个线段的部分既有一段相乘一个数，又有一段相加上一个数，还有中间会询问一段区间的和是多少？

题解：如果只有一段相加上一个数，那么很显然，很板的LAZY操作，但是现在又有了相乘一个数的操作，还在LAZY操作进行解决

现在区间不仅有加法，还有乘法，区间和的形式应该为：ax+b，表示现在的区间和是原来的区间和先乘以a再加上b。

在程序中我们把mu定义为a，sum定义成su，ad定义为b，下传标记时节点的更新就是su = mu * su + ad

当我们要修改一个区间时，要保证ax+b的形式，即先乘后加的形式。当将区间乘以一个数k时，原来的区间和为ax+b，乘以k得k(ax+b)=kax+kb，也就是把节点的su和ad都乘上一个k。

区间加一个数更加简单，原来的区间和为ax+b，加上一个k为ax+b+k，合并b, k得ax+(b+k)，也就是把原来的ad加上一个k。

我们设要下传标记的节点的ad为b，mu为a，因此这个节点的和为ax+b，它的一个儿子的ad为b'，mu为a'，这个节点的和为a'y+b'，为了保持先乘后加的顺序，先把该节点的和乘以a得aa'y+ab'然后加上b得aa'y+ab'+b合并一下得(aa')y+(ab'+b)也就是把这个节点的儿子的mu乘以这个节点的mu，然后把这个节点的儿子的ad乘以这个节点的mu再加上这个节点的ad，更新这个节点，清空这个节点的标记，然后标记就下传完毕了。

附上代码：

#include<bits/stdc++.h>

using namespace std;

#define update tr[t].su=tr[t<<1].su+tr[t<<1|1].su;tr[t].su%=M;

typedef long long ll;

const int N=1e5+50;

struct node{
    ll mu,su,ad;
}tr[N<<2];

int n,M,a[N],op,x,y,m;

ll read(){
    ll x=0;
    char ch;
    do{
       ch=getchar();
    }while (ch<'0'||ch>'9');
    while (ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}

void build(int t,int l,int r){
    tr[t].mu=1;
    if (l==r){
        tr[t].su=a[l];
        return;
    }
    int mid=l+r>>1;
    build(t<<1,l,mid);
    build(t<<1|1,mid+1,r);
    update;
}
void maintain(int t,int k){
    tr[t<<1].su=(tr[t<<1].su*tr[t].mu+tr[t].ad*(k+1>>1))%M;
    tr[t<<1|1].su=(tr[t<<1|1].su*tr[t].mu+tr[t].ad*(k>>1))%M;
    tr[t<<1].mu=tr[t<<1].mu*tr[t].mu%M;
    tr[t<<1|1].mu=tr[t<<1|1].mu*tr[t].mu%M;
    tr[t<<1].ad=(tr[t<<1].ad*tr[t].mu+tr[t].ad)%M;
    tr[t<<1|1].ad=(tr[t<<1|1].ad*tr[t].mu+tr[t].ad)%M;
    tr[t].mu=1;tr[t].ad=0;
}

void cheng(int t,int l,int r,ll val){
    if (x<=l && r<=y){
        tr[t].mu=tr[t].mu*val%M;
        tr[t].ad=tr[t].ad*val%M;
        tr[t].su=tr[t].su*val%M;
        return;
    }
    maintain(t,r-l+1);
    int mid=l+r>>1;
    if(x>mid){
        cheng(t<<1|1,mid+1,r,val);
    }else if(y<=mid){
        cheng(t<<1,l,mid,val);
    }else{
        cheng(t<<1,l,mid,val);
        cheng(t<<1|1,mid+1,r,val);
    }
    update;
}
void jia(int t,int l,int r,ll val){
    if (x<=l && r<=y){
        tr[t].ad+=val;
        tr[t].ad%=M;
        tr[t].su=(tr[t].su+(r-l+1)*val)%M;
        return;
    }
    maintain(t,r-l+1);
    int mid=l+r>>1;
    if(x>mid){
        jia(t<<1|1,mid+1,r,val);
    }else if(y<=mid){
        jia(t<<1,l,mid,val);
    }else{
        jia(t<<1,l,mid,val);
        jia(t<<1|1,mid+1,r,val);
    }
    update;
}
ll query(int t,int l,int r){
    if (x<=l && r<=y){
        return tr[t].su;
    }
    maintain(t,r-l+1);
    int mid=l+r>>1;
    ll ans=0;
    if(x>mid){
        ans+=query(t<<1|1,mid+1,r);
    }else if(y<=mid){
        ans+=query(t<<1,l,mid);
    }else{
        ans+=query(t<<1,l,mid);
        ans+=query(t<<1|1,mid+1,r);
    }
    ans%=M;
    return ans;
}
int main(){
    n=read();M=read();
    for (int i=1;i<=n;i++){
        a[i]=read();
    }
    build(1,1,n);
    m=read();
    while (m--){
        op=read();x=read();y=read();
        if (op==1){
           cheng(1,1,n,read());
        }else if (op==2){
            jia(1,1,n,read());
        }else{
            printf("%lld\n",query(1,1,n));
        }
    }
    return 0;
}