D 线段树 区间加，区间乘，区间查询，区间覆盖

这题写了我两个小时，在cf延时的15分钟内调出来了，直呼内行
D 线段树 区间加，区间乘，区间查询，区间覆盖
给个节点用k*x+val 表示lazy更新 初始叶子节点k=1 val=a[l] 其他 k=1 val=0

一个mul数组，记录每个节点的前面的系数k，val数组记录后面val的值 sum数组记录区间和，因为询问的是区间和

每次区间乘了一个k：

某个节点记录：

mul[id]*=k

val[id]*=k

sum[id]*=k

mul[id]=k*mul[id]%mod;
val[id]=k*val[id]%mod;
sum[id]=k*sum[id]%mod;

区间加了一个k:

val[id]+=k

sum[id]+k*(r-l+1） (l,r是某个节点的信息）

add(val[id],k);
add(sum[id],k*(r-l+1)%mod);

区间覆盖：（惊天妙手，突然想到的处理方式）

mul[id]=0;
val[id]=k;
sum[id]=k*(r-l+1)

lazy更新：相当于某个节点同时来k倍系数以及加了个 后缀的x值

假设k、x是由id的父亲节点传来，

mul[id]*=k;

val[id]=x+k*val[id]

sum[id]=sum[id]k+x(r-l+1)

int root=id,len=r-l+1;

ll p=mod;
mul[id<<1]=mul[id]*mul[id<<1]%mod;
val[id<<1]=(val[id]+val[id<<1]*mul[id]%mod)%mod;
sum[root<<1]=(sum[root<<1]*mul[root]%p+val[root]*(len-(len>>1))%p)%p;

mul[id<<1|1]=mul[id]*mul[id<<1|1]%mod;
val[id<<1|1]=(val[id]+val[id<<1|1]*mul[id]%mod)%mod;
sum[root<<1|1]=(sum[root<<1|1]*mul[root]%p+val[root]*(len>>1)%p)%p;

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline ll read()
{
    ll x=0,w=1; char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
    return w==1?x:-x;
}
const int N=2e5+10;
ll n,m,mod;
int mx;
struct node
{
    int ty,l,r;
    ll k;
}a[N];
ll mul[4*N],val[4*N],sum[4*N],t[N];
int st[4*N];
void add(ll &x,ll y)
{
    x=(x+y)%mod;
}
void build(int id,int l,int r)
{
    mul[id]=1;
    if(l==r){
       sum[id]=t[l];
        return ;
    }
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
    sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
}
void pushdown(int id,int l,int r)
{
    int mid=l+r>>1;

    if(mul[id]==1&&val[id]==0) return;


    int root=id,len=r-l+1;
    ll p=mod;
    mul[id<<1]=mul[id]*mul[id<<1]%mod;
    val[id<<1]=(val[id]+val[id<<1]*mul[id]%mod)%mod;
    sum[root<<1]=(sum[root<<1]*mul[root]%p+val[root]*(len-(len>>1))%p)%p;

    mul[id<<1|1]=mul[id]*mul[id<<1|1]%mod;
    val[id<<1|1]=(val[id]+val[id<<1|1]*mul[id]%mod)%mod;
    sum[root<<1|1]=(sum[root<<1|1]*mul[root]%p+val[root]*(len>>1)%p)%p;

    mul[id]=1,val[id]=0;
}
ll qu(int id,int l,int r,int ql,int qr)
{
    if(ql<=l&&r<=qr) return sum[id];
    int mid=l+r>>1;
    ll ans=0;
    pushdown(id,l,r);
    if(ql<=mid) ans=qu(id<<1,l,mid,ql,qr);
    if(qr>mid) add(ans,qu(id<<1|1,mid+1,r,ql,qr));
    //sum[id]=(sum[id<<1|1]+sum[id<<1])%mod;
    return ans;
}

void up(int id,int l,int r,int ql,int qr,ll k,int ty)
{
    if(ql<=l&&r<=qr){
        if(ty==1){
            //printf("id:%d sum[id]:%lld\n",id,sum[id]);

            add(val[id],k);
            add(sum[id],k*(r-l+1)%mod);
            //printf("id:%d sum[id]:%lld\n",id,sum[id]);
        }
        else if(ty==2){
            mul[id]=k*mul[id]%mod;
            val[id]=k*val[id]%mod;
            sum[id]=k*sum[id]%mod;
        }
        else if(ty==3){
            st[id]=-1;
            mul[id]=0;
            val[id]=k;
            sum[id]=k*(r-l+1)%mod;
        }
        else{
            mul[id]=1,val[id]=k;

            sum[id]=k*(r-l+1)%mod;
        }
        return ;
    }
    pushdown(id,l,r);
    int mid=l+r>>1;
    if(ql<=mid) up(id<<1,l,mid,ql,qr,k,ty);
    if(qr>mid) up(id<<1|1,mid+1,r,ql,qr,k,ty);
    sum[id]=(sum[id<<1|1]+sum[id<<1])%mod;
}
int main()
{
    n=read(),m=read(),mod=read();
    mx=n;
    rep(i,1,n) t[i]=read();

    for(int i=1;i<=m;++i){
        scanf("%d%d",&a[i].ty,&a[i].l);
        if(a[i].ty==5) scanf("%d",&a[i].r);
        else if(a[i].ty==4) mx++;
        else scanf("%d%lld",&a[i].r,&a[i].k),a[i].k%=mod;
        a[i].r=min(a[i].r,mx);
        a[i].r=min(a[i].r,mx);
    }

    build(1,1,mx);

    int now=n;
    for(int i=1;i<=m;++i){
        if(a[i].ty==1){
           up(1,1,mx,a[i].l,a[i].r,a[i].k,1);
        }
        else if(a[i].ty==2){
           up(1,1,mx,a[i].l,a[i].r,a[i].k,2);
        }
        else if(a[i].ty==3){
           up(1,1,mx,a[i].l,a[i].r,a[i].k,3);
        }
        else if(a[i].ty==4){
           up(1,1,mx,++now,now,a[i].l,4);
        }
        else if(a[i].ty==5){
           printf("%lld\n",qu(1,1,mx,a[i].l,a[i].r));
        }
    }
}
/*
5 6 9555
1 1 1 1 1
3 2 5 5
5 1 5
1 1 4 5
1 1 5 5
1 3 5 5
5 1 4
5 12 9555
1 1 1 1 1
3 2 5 5
1 1 4 5
1 1 5 5
1 3 5 5
5 1 4
2 1 5 5
2 2 2 5
3 5 5 5
3 3 5 5
5 1 3
1 2 3 5
5 1 3
*/