P3373 【模板】线段树 2（区间乘+加操作，先乘后加原则）

yongchaoD / 2024-07-19 / 原文

题目来源：https://www.luogu.com.cn/problem/P3373
//
题意：对区间[l,r]可以乘法，加法操作，查询和操作。
//
思路：既有乘法又有加法，肯定是要有两个标记。纯加法和纯乘法操作是很简单的，但是既有乘法又有加法涉及到先乘后加和先加后乘的顺序。
//

//

//
所以现在是如何将先加后成也可以转为lazy标记先乘后加也是正确的：
//

//
题解：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;
vector<int>tree(4*N,0),arr(N,0),add(4*N,0),mul(4*N,1);
int n,q,Mod,op,x,y,k;

int lp(int p){return p<<1;}//2*p
int rp(int p){return p<<1 |1;}//2*p+1

void pushup(int p){
    tree[p]=tree[lp(p)]+tree[rp(p)];
    tree[p]%=Mod;
}

void tag_mul(int p,int c){
    add[p]*=c,add[p]%=Mod;//标记mul的当前节点有add标记，add标记需要*=c。就算没有add标记（=0），*=c，也等于0
    mul[p]*=c,mul[p]%=Mod;//mul标记
    tree[p]*=c,tree[p]%=Mod;
}

void pushdown(int p,int len){//下传标记(mul,add),先乘后加
   if(mul[p]!=1){//mul下传
       tag_mul(lp(p),mul[p]);
       tag_mul(rp(p),mul[p]);
        mul[p]=1;
   }
    if(add[p]!=0){//add下传
        add[lp(p)]+=add[p],add[lp(p)]%=Mod;
        add[rp(p)]+=add[p],add[rp(p)]%=Mod;
         tree[lp(p)]+=(len-(len>>1))*add[p],tree[lp(p)]%=Mod;//len是p节点的子节点的区间 。lp:(len-(len>>1)) , rp:(len>>1)
         tree[rp(p)]+=(len>>1)*add[p],tree[rp(p)]%=Mod;
          add[p]=0;
    }
}

void build(int s,int t,int p){
    if(s==t){
        tree[p]=arr[s],tree[p]%=Mod;
        return;
    }
     int m=(s+t)>>1;
     build(s,m,lp(p)),build(m+1,t,rp(p));
     pushup(p);
}

void update(int l,int r,int c,int s,int t,int p){
    if(l<=s && r>=t){
        if(op==1){tag_mul(p,c);}//乘法:mul标记
        else if(op==2){//加法：add标记
           add[p]+=c,add[p]%=Mod;
           tree[p]+=(t-s+1)*c,tree[p]%=Mod;
        }
        return;
    }
     pushdown(p,t-s+1);//len=t-s+1
    int m=(s+t)>>1;
     if(l<=m) {update(l,r,c,s,m,lp(p));}
     if(r>=m+1) {update(l,r,c,m+1,t,rp(p));}
     pushup(p);
}

int getsum(int l,int r,int s,int t,int p){
    if(l<=s && r>=t){
       return tree[p];
    }
    pushdown(p,t-s+1);
    int m=(s+t)>>1,sum=0;
    if(l<=m) {
        sum=getsum(l,r,s,m,lp(p));
        sum%=Mod;
    }
    if(r>=m+1) {
        sum+=getsum(l,r,m+1,t,rp(p));
        sum%=Mod;
    }
     return sum%Mod;
}

signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q>>Mod;
     for(int i=1;i<=n;i++) cin>>arr[i];
      build(1,n,1);

       while(q--){
           cin>>op;
           if(op==1 || op==2){//[x,y]*k, +k
              cin>>x>>y>>k;
               update(x,y,k,1,n,1);
           }
           if(op==3){
              cin>>x>>y;//查询[x,y]
               cout<<getsum(x,y,1,n,1)<<'\n';
           }
       }
    return 0;
}