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

SFWR · 2018-12-22 10:07:00 · 题解

蒟蒻的第二篇题解== 本题和上一道模板题3373还是有很大不同的 当然加法没有变 乘法的话要注意，之前加的值实际上已经算在原区间里了，所以乘法是要对这个进行操作的 依旧是不用结构体的数组 还要注意乘法的tag要初定义为1 以及，在乘法操作时已经将加法乘了，所以不要再乘一次，所以先乘再加 上代码求过审

#include<bits/stdc++.h>
using namespace std;
int n,m,t,x,y,cnt,z,p,c;
const int MAXN=100001;
long long sum[MAXN*4],a[MAXN];
long long tag[MAXN*4],tag2[MAXN*4];
void build(int now,int l,int r){
    if(l==r){cnt++;sum[now]=a[cnt];}else{
        int mid=(l+r)/2;
        build(now<<1,l,mid);
        build(now<<1|1,mid+1,r);
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
}
void push_down1(int now){//*
    if(tag[now]!=1){
        sum[now<<1]=sum[now<<1]*tag[now]%p;
        sum[now<<1|1]=sum[now<<1|1]*tag[now]%p;
        tag[now<<1]=tag[now<<1]*tag[now]%p;
        tag[now<<1|1]=tag[now<<1|1]*tag[now]%p;
        tag2[now<<1]=tag2[now<<1]*tag[now]%p;
        tag2[now<<1|1]=tag2[now<<1|1]*tag[now]%p;
        tag[now]=1;
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
}
void push_down2(int now,int l,int r){//+
    if(tag2[now]!=0){
        int mid=(l+r)/2;
        sum[now<<1]=(sum[now<<1]+(mid-l+1)*tag2[now]*tag[now])%p;
        sum[now<<1|1]=(sum[now<<1|1]+(r-mid)*tag2[now]*tag[now])%p;
        tag2[now<<1]=(tag2[now<<1]+tag2[now])%p;
        tag2[now<<1|1]=(tag2[now<<1|1]+tag2[now])%p;
        tag2[now]=0;
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
}
void update1(int now,int l,int r,int q_l,int q_r,long long x){//**
    if(q_l<=l&&q_r>=r){
        sum[now]=(sum[now]*x)%p;
        tag2[now]=(tag2[now]*x)%p;
        tag[now]=(tag[now]*x)%p;
    }else{push_down1(now);
        push_down2(now,l,r);
        int mid=(l+r)/2;
        if(q_l<=mid)update1(now<<1,l,mid,q_l,q_r,x);
        if(q_r>mid)update1(now<<1|1,mid+1,r,q_l,q_r,x);
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
}
void update2(int now,int l,int r,int q_l,int q_r,long long x){//++
    if(q_l<=l&&q_r>=r){
        sum[now]=(sum[now]+(r-l+1)*x)%p;
        tag2[now]=(tag2[now]+x)%p;
    }else{push_down1(now);
        push_down2(now,l,r);
        int mid=(l+r)/2;
        if(q_l<=mid)update2(now<<1,l,mid,q_l,q_r,x);
        if(q_r>mid)update2(now<<1|1,mid+1,r,q_l,q_r,x);
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
}
long long get_sum(int now,int l,int r,int q_l,int q_r){
    long long re=0;
    if(q_l<=l&&q_r>=r)re+=sum[now];else{
        push_down1(now);
        push_down2(now,l,r);
        int mid=(l+r)/2;
        if(q_l<=mid)re+=get_sum(now<<1,l,mid,q_l,q_r);
        if(q_r>mid)re+=get_sum(now<<1|1,mid+1,r,q_l,q_r);
        sum[now]=(sum[now<<1]+sum[now<<1|1])%p;
    }
    return re;
}
int main(){
    cin>>n>>m>>p;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<=MAXN*4;i++)tag[i]=1;
    build(1,1,n);
    while(m!=0){
        cin>>t;
        if(t==1){
            cin>>x>>y>>z);
            update1(1,1,n,x,y,z);}
        if(t==2){cin>>x>>y>>z);
            update2(1,1,n,x,y,z);}
        if(t==3){
            cin>>x>>y;
            cout<<get_sum(1,1,n,x,y)%p<<endl;
        }
        m--;
    }
}