线段树 （区间修改 区间查询） 加法和乘法

https://www.luogu.com.cn/problem/P3373

#include<bits/stdc++.h> 
#define N 100005
#define endl '
' 
#define _for(i,a,b) for(int i=a;i<b;i++)
using namespace std;
typedef long long ll; 
ll n,m,p,x,y,k,ch;
ll a[N];
struct Node{
    int l,r; 
    ll mul,add,sum;
}T[N*4];
void Build(int v,int l,int r){
    T[v].l=l; T[v].r=r; T[v].add=0; T[v].mul=1;
    if( l==r ){
        T[v].sum=a[l];
        return ;
    }
    int mid=(l+r)/2;
    Build(v*2,l,mid);
    Build(v*2+1,mid+1,r);
    T[v].sum=(T[v*2].sum+T[v*2+1].sum)%p;
}
void push_down(int v){
    ll k1=T[v].mul,k2=T[v].add;
    T[v*2].sum=( T[v*2].sum*k1+k2*(T[v*2].r-T[v*2].l+1) )%p; 
    T[v*2].mul=( T[v*2].mul*k1 )%p;
    T[v*2].add=( T[v*2].add*k1+k2 )%p;
    T[v*2+1].sum=( T[v*2+1].sum*k1+k2*(T[v*2+1].r-T[v*2+1].l+1) )%p; 
    T[v*2+1].mul=( T[v*2+1].mul*k1 )%p;
    T[v*2+1].add=( T[v*2+1].add*k1+k2 )%p;
    T[v].add=0,T[v].mul=1;
}
void Add(int v,int l,int r,int k){
    if( T[v].l>=l && T[v].r<=r ){
        T[v].sum= ( T[v].sum+( (T[v].r-T[v].l+1)*k ) )%p ;
        T[v].add=(T[v].add+k)%p;
        return ;
    }
    if( T[v].r<l || T[v].l>r ) return ;
    push_down(v);
    if( T[v*2].r>=l ) Add(v*2,l,r,k);
    if( T[v*2+1].l<=r ) Add(v*2+1,l,r,k);
    T[v].sum= (T[v*2].sum+T[v*2+1].sum)%p;
}
void Multiply(int v,int l,int r,int k){
    if( T[v].l>=l && T[v].r<=r ){
        T[v].mul=(T[v].mul*k)%p;
        T[v].sum=(T[v].sum*k)%p;
        T[v].add=(T[v].add*k)%p;
        return ;
    }
    if( T[v].r<l || T[v].l>r ) return ;
    push_down(v);
    if( T[v*2].r>=l ) Multiply(v*2,l,r,k);
    if( T[v*2+1].l<=r ) Multiply(v*2+1,l,r,k);
    T[v].sum= (T[v*2].sum+T[v*2+1].sum)%p;
}
 
ll search(int v,int l,int r){
    if( T[v].l>=l && T[v].r<=r ){ 
        return T[v].sum;
    }
    if( T[v].r<l || T[v].l>r ) return 0;
    push_down(v);
    ll res=0;
    if( T[v*2].r>=l ) res+=search(v*2,l,r); 
    if( T[v*2+1].l<=r ) res+=search(v*2+1,l,r);
    return res%p;
}

int main(){    
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    
    cin>>n>>m>>p;
    _for(i,1,n+1) cin>>a[i];
    Build(1,1,n);
    while(m--){
        cin>>ch>>x>>y;
        if( ch==1 ){
            cin>>k; k%=p;
            Multiply(1,x,y,k);
        }
        else if( ch==2 ){
            cin>>k; k%=p;
            Add(1,x,y,k);
        }
        else{
            cout<<search(1,x,y)<<endl;
        }
    } 
    return 0;
}