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

· · 题解

标准的线段树模板，最基础的应用看着简单然而有需要注意的地方

特别要注意几点（都是自己写时改了很多遍的地方）：

1、开long long

2、如果定义mid的话一定要加()

3、下传2个标记时一定要注意先乘后加 ， 不然一定错

关于常数优化，除了位运算，也可以少 MOD 几次，似乎能加快（然而我并用不来）

#include<bits/stdc++.h>
#define rep(i,j,n) for(int i=j;i<=n;i++)
using namespace std;
typedef long long ll;
const int N=100010;
int n,m,type,x,y , mod;
ll tree[N<<2],addv[N<<2],mul[N<<2],c[N], k;   //四倍空间
#define lson o<<1
#define rson o<<1|1
#define mid (l+r>>1)  //为了偷懒。。
inline void up(int o) { tree[o]=tree[lson]+tree[rson] ; }  //合并区间信息
inline void build(int o,int l,int r) {
    mul[o]=1;
    if(l==r) { tree[o]=c[l]%mod; return ;}
    build(lson,l,mid) ; build(rson,mid+1,r) ; up(o);
}
inline void down(int o,int l,int r,int ls,int rs) {  //下传2个lazytag
    if(mul[o]!=1) {   //注意先乘后加
        ll x=mul[o] ; mul[o]=1;  //这里的中间变量也一定要开long long 
        (addv[ls]*=x) %=mod ; (mul[ls]*=x) %=mod ; (tree[ls]*=x) %=mod;
        (addv[rs]*=x) %=mod ; (mul[rs]*=x) %=mod ; (tree[rs]*=x) %=mod;
    }
    if(addv[o]!=0) {
        ll x=addv[o] ; addv[o]=0;
        (addv[ls]+=x) %=mod ; (tree[ls]+=x*(mid-l+1)) %=mod;
        (addv[rs]+=x) %=mod ; (tree[rs]+=x*(r - mid)) %=mod;
    }
}
inline void update(int o,int l,int r,int L,int R ,ll x, int type) {
    if(L<=l && r<=R ) {
        if(type==2) (addv[o]+=x)%=mod , (tree[o]+=x*(r-l+1)) %=mod ;
        else (addv[o]*=x) %=mod , (mul[o]*=x) %=mod , (tree[o]*=x) %=mod; return ;
    }
    down(o,l,r,lson,rson) ;
    if(L<=mid) update(lson,l,mid,L,R,x,type); 
    if(R>mid) update(rson,mid+1,r,L,R,x,type);
    up(o) ;
}
inline ll query(int o,int l,int r,int L,int R ){
    if(L<=l && r<=R ) return tree[o] ;
    down(o,l,r,lson,rson) ; ll ret =0 ;
    if(L<=mid)  (ret+=query(lson,l,mid,L,R) ) %=mod;
    if(R>mid) (ret+=query(rson,mid+1,r,L,R) ) %=mod;
    return ret; 
}
int main() {
    scanf("%d%d%d",&n,&m,&mod);
    rep(i,1,n) scanf("%lld",&c[i]) ;
    build(1,1,n) ;
    while(m--) {
        scanf("%d",&type);
        if(type==3) scanf("%d%d",&x,&y) , printf("%lld\n",query(1,1,n,x,y)) ;
        else scanf("%d%d%lld",&x,&y,&k) , update(1,1,n,x,y,k,type);
    }
    return 0;
}