线段树2

Oliver_Heldens · 2019-08-08 19:08:43 · 题解

两个lazy_tag的原因主要是加法和乘法难以同时维护，并且优先级不同；左儿子和右儿子用位运算优化一下

#include<bits/stdc++.h>
#define lson (o<<1)
#define rson (o<<1|1)
using namespace std;
int n,m,p,x,y,ch;
long long k,a[100007];
struct node{
long long v, mul, add;
}st[400007];
void build(int o, int l, int r){
    st[o].mul=1;//初始状态 
    st[o].add=0;
    if(l==r){st[o].v=a[l];return;}//赋值 
    int m=(l+r)>>1; 
    build(lson,l,m);//建左右子树 
    build(rson,m+1,r);
    st[o].v=st[lson].v+st[rson].v;//求和 
    st[o].v%=p;
}
void pushdown(int o,int l,int r){//下放lazy_tag 
    int m=(l+r)>>1; 
    st[lson].v=(st[lson].v*st[o].mul+st[o].add*(m-l+1))%p;//下放 
    st[rson].v=(st[rson].v*st[o].mul+st[o].add*(r-m))%p; 
    st[lson].mul=(st[lson].mul*st[o].mul)%p;//修改乘法标记 
    st[rson].mul=(st[rson].mul*st[o].mul)%p;
    st[lson].add=(st[lson].add*st[o].mul+st[o].add)%p;//修改加法标记 
    st[rson].add=(st[rson].add*st[o].mul+st[o].add)%p;
    st[o].mul=1;//恢复初始状态 
    st[o].add=0;
}
void update(int o,int l,int r,int left,int right,long long k){//区间乘
if(l>=left&&r<=right){//修改区间和、加法和乘法标记 
    st[o].v=(st[o].v*k)%p;
    st[o].mul=(st[o].mul*k)%p;
    st[o].add=(st[o].add*k)%p;
    return;
}
pushdown(o,l,r);//下放 
int m=(l+r)>>1;
if(m>=left)update(lson,l,m,left,right,k); //符合条件就继续递归 
if(m<right)update(rson,m+1,r,left,right,k);
st[o].v=(st[lson].v+st[rson].v)%p;
}
void update1(int o,int l,int r,int left,int right,long long k){//区间加 
if(l>=left&&r<=right){//修改区间和和加法标记 
    st[o].add=(st[o].add+k)%p;
    st[o].v=(st[o].v+k*(r-l+1))%p;
    return;
}
pushdown(o,l,r);//下放 
int m=(l+r)>>1;
if(m>=left)update1(lson,l,m,left,right,k); //符合条件就继续递归 
if(m<right)update1(rson,m+1,r,left,right,k);
st[o].v=(st[lson].v+st[rson].v)%p;
}
long long query(int o,int left,int right,int l,int r){//区间求和 
if(r<left||right<l)return 0;
if(l<=left&&right<=r)return st[o].v;
pushdown(o,left,right);
int m=(left+right)/2;
return (query(lson,left,m,l,r)+query(rson,m+1,right,l,r))%p;
}
int main(){
scanf("%d%d%d",&n,&m,&p);
for(int i=1;i<=n;i++)
    scanf("%lld",&a[i]);
build(1,1,n);
while(m--){
    scanf("%d",&ch);
    if(ch==1){
        scanf("%d%d%lld",&x,&y,&k);
        update(1,1,n,x,y,k);
    }
    else if(ch==2){
        scanf("%d%d%lld",&x,&y,&k);
        update1(1,1,n,x,y,k);
    }
    else{
        scanf("%d%d",&x,&y);
        printf("%lld\n",query(1,1,n,x,y));
    }
}
return 0;
}