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

好耶，花了将近一上午，且在\(Quick\)_\(AK\)的帮助在a了这道模板题

简要思路

这道模板题有两个区间操作

• 将某区间每一个数乘上 x
• 将某区间每一个数加上 x

有两种操作，那岂不是要两个\(tag\)?

(⊙v⊙)嗯，是的

举个栗子：

假设我们维护一个量\(a\),它有两个标记\(+b\)和\(*c\)

因为线段树可以维护支持结合律的数据...(省略一万个字)，所以我们要先乘后加

谔谔，都说了是简要思路

#include 
#include 
#include 
#include 
#define ls p<<1
#define int long long
#define rs p<<1|1
using namespace std;
int n,m,a[4000005],dat[4000005],lazy1[4000005];
int lazy2[4000005];
int pp;
int q;
inline int read(){
  int x=0;int f=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
  return x*f;
}
inline void down(int p,int l,int r){
  int mid=l+r>>1;
  dat[ls]*=lazy1[p],dat[rs]*=lazy1[p];
  dat[ls]%=pp,dat[rs]%=pp;
  dat[ls]+=lazy2[p]*(mid-l+1),dat[rs]+=lazy2[p]*(r-mid);
  dat[ls]%=pp,dat[rs]%=pp;
  lazy1[ls]*=lazy1[p],lazy1[rs]*=lazy1[p];
  lazy1[ls]%=pp,lazy1[rs]%=pp;
  lazy2[ls]*=lazy1[p],lazy2[rs]*=lazy1[p];
  lazy2[ls]%=pp,lazy2[rs]%=pp;
  lazy2[ls]+=lazy2[p],lazy2[rs]+=lazy2[p];
  lazy2[ls]%=pp,lazy2[rs]%=pp;
  lazy1[p]=1;
  lazy2[p]=0;
}
inline void build(int p,int l,int r){
  lazy1[p]=1;
  if(l==r) {dat[p]=a[l];return;}
  int mid=(l+r)>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  dat[p]=(dat[ls]+dat[rs])%pp;
}
inline void update1(int p,int x,int y,int l,int r,int k){
  if(x<=l&&y>=r){
    dat[p]*=k;
    dat[p]%=pp;
    lazy1[p]*=k;
    lazy1[p]%=pp;
    lazy2[p]*=k;
    lazy2[p]%=pp;
    return;
  }
  down(p,l,r);
  int mid=l+r>>1;
  if(x<=mid) update1(ls,x,y,l,mid,k);
  if(y>mid) update1(rs,x,y,mid+1,r,k);
  dat[p]=(dat[ls]+dat[rs])%pp;
}
inline void update2(int p,int x,int y,int l,int r,int k){
  if(x<=l&&y>=r){
    dat[p]+=k*(r-l+1);
    dat[p]%=pp;
    lazy2[p]+=k;
    lazy2[p]%=pp;
    return;
  }
  down(p,l,r);
  int mid=l+r>>1;
  if(x<=mid) update2(ls,x,y,l,mid,k);
  if(y>mid) update2(rs,x,y,mid+1,r,k);
  dat[p]=(dat[ls]+dat[rs])%pp;
}
inline int query(int p,int x,int y,int l,int r){
  int res=0;
  if(x<=l&&y>=r) return dat[p]%pp;
  int mid=l+r>>1;
  down(p,l,r);
  if(x<=mid) (res+=query(ls,x,y,l,mid))%pp;
  if(y>mid) (res+=query(rs,x,y,mid+1,r))%pp;
  return res%pp;
}
signed main(){
  n=read();m=read();pp=read();
  for(int i=1;i<=n;i++)
    a[i]=read();
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int c,x,k,y;
    c=read();
    if(c==1){
    x=read();y=read();k=read();
    update1(1,x,y,1,n,k);
    }
    if(c==2){
      x=read();y=read();k=read();
      update2(1,x,y,1,n,k);
    }
    if(c==3){
      x=read();y=read();
      cout<