题解 P3373 【【模板】线段树 2】

· · 题解

线段树练习啊.....虽然有两个lazy标记，但是只要我们确定它们的先后顺序就没有那么难了。我们可以每次在更新乘法标记时也更新加法标记，然后标记下放时先放乘法标记，再放加法标记就可以了。

第一次没有A是因为取模的问题，改了一下就好了，取模不要太频繁。

题解里有人说除非是玄学大佬不然会T....不过真的不用玄学大佬啊，加个读入优化就过了.....读入优化是神器，可以迅速缩短时间。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
ll read(){
    ll w=1,q=0;char ch=' ';
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')q=(ll)q*10+ch-'0',ch=getchar();
    return (ll)w*q;
}
int n,m;
ll mod;
ll a[100005],sum[400005],mul[400005],laz[400005];
void up(int i){sum[i]=(sum[(i<<1)]+sum[(i<<1)|1])%mod;}
void pd(int i,int s,int t){//精髓所在，先放乘法再放加法
    int l=(i<<1),r=(i<<1)|1,mid=(s+t)>>1;
    if(mul[i]!=1){
    mul[l]*=mul[i];mul[l]%=mod;mul[r]*=mul[i];mul[r]%=mod;
    laz[l]*=mul[i];laz[l]%=mod;laz[r]*=mul[i];laz[r]%=mod;
    sum[l]*=mul[i];sum[l]%=mod;sum[r]*=mul[i];sum[r]%=mod;
    mul[i]=1;
    }
    if(laz[i]){
    sum[l]+=laz[i]*(mid-s+1);sum[l]%=mod;
    sum[r]+=laz[i]*(t-mid);sum[r]%=mod;
    laz[l]+=laz[i];laz[l]%=mod;
    laz[r]+=laz[i];laz[r]%=mod;
    laz[i]=0;
    }return;
}
void build(int s,int t,int i){
    mul[i]=1;if(s==t){sum[i]=a[s];return;}
    int mid=(s+t)>>1;
    build(s,mid,i<<1);build(mid+1,t,(i<<1)|1);up(i);
}
void chen(int l,int r,int s,int t,int i,ll z){
    int mid=(s+t)>>1;
    if(l<=s&&t<=r){
        mul[i]*=z;mul[i]%=mod;laz[i]*=z;laz[i]%=mod;//更新乘法的同时更新加法
        sum[i]*=z;sum[i]%=mod;return;
    }
    pd(i,s,t);
    if(mid>=l)chen(l,r,s,mid,(i<<1),z);
    if(mid+1<=r)chen(l,r,mid+1,t,(i<<1)|1,z);
    up(i);
}
void add(int l,int r,int s,int t,int i,ll z){
    int mid=(s+t)>>1;
    if(l<=s&&t<=r){
        sum[i]+=z*(t-s+1);sum[i]%=mod;laz[i]+=z;laz[i]%=mod;
        return;
    }
    pd(i,s,t);
    if(mid>=l)add(l,r,s,mid,(i<<1),z);
    if(mid+1<=r)add(l,r,mid+1,t,(i<<1)|1,z);
    up(i);
}
ll getans(int l,int r,int s,int t,int i){
    int mid=(s+t)>>1;ll tot=0;
    if(l<=s&&t<=r){return sum[i];}
    pd(i,s,t);
    if(mid>=l)tot+=getans(l,r,s,mid,(i<<1));
    tot%=mod;
    if(mid+1<=r)tot+=getans(l,r,mid+1,t,(i<<1)|1);
    return tot%mod;
}
int main()
{
    int i,j,x,y,bh;
    ll z;
    n=read();m=read();mod=read();
    for(i=1;i<=n;i++)a[i]=read();
    build(1,n,1);
    for(i=1;i<=m;i++){
        bh=read();
        if(bh==1){
            x=read();y=read();z=read();
            chen(x,y,1,n,1,z);
        }
        else if(bh==2){
            x=read();y=read();z=read();
            add(x,y,1,n,1,z);
        }
        else if(bh==3){
            x=read();y=read();
            printf("%lld\n",getans(x,y,1,n,1));
        }
    }
       return 0;
}