洛谷 P3373 【模板】线段树 2

​​题目传送门​​

#include<bits/stdc++.h>
using namespace std;

#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
typedef long long ll;
const int maxn=100000+100;

struct Tree{
  
  ll v,mul,add;
}tree[maxn<<2];
ll ans[maxn],p;
int n,m;

void build(int root,int l,int r){
  
  if(l==r){
    
    tree[root].v=ans[l]%p;
    tree[root].mul=1;
    tree[root].add=0;
    return ;
  }
  tree[root].mul=1;
  tree[root].add=0;
  int mid=(l+r)>>1;
  build(lson);
  build(rson);
  tree[root].v=(tree[root<<1].v+tree[root<<1|1].v)%p;
}

void updateUp(int root,int l,int r,int mid){
  
  tree[root<<1].v=(tree[root<<1].v*tree[root].mul+tree[root].add*(mid-l+1))%p;
  tree[root<<1].mul=(tree[root<<1].mul*tree[root].mul)%p;
  tree[root<<1].add=(tree[root<<1].add*tree[root].mul+tree[root].add)%p;
  tree[root<<1|1].v=(tree[root<<1|1].v*tree[root].mul+tree[root].add*(r-mid))%p;
  tree[root<<1|1].mul=(tree[root<<1|1].mul*tree[root].mul)%p;
  tree[root<<1|1].add=(tree[root<<1|1].add*tree[root].mul+tree[root].add)%p;
  tree[root].mul=1;
  tree[root].add=0;
}

void updateAdd(int root,int l,int r,int L,int R,ll v){
  
  if(L>r || R<l) return ;
  if(L<=l && R>=r){
    
    tree[root].v=(tree[root].v+v*(r-l+1))%p;
    tree[root].add=(tree[root].add+v)%p;
    return ;
  } 
  
  int mid=(l+r)>>1;
  if(tree[root].add || tree[root].mul!=1) updateUp(root,l,r,mid);
  updateAdd(lson,L,R,v);
  updateAdd(rson,L,R,v);
  tree[root].v=(tree[root<<1].v+tree[root<<1|1].v)%p;
}

void updateMul(int root,int l,int r,int L,int R,ll v){
  
  if(L>r || R<l) return ;
  if(L<=l && R>=r){
    
    tree[root].v=(tree[root].v*v)%p;
    tree[root].mul=(tree[root].mul*v)%p;
    tree[root].add=(tree[root].add*v)%p;
    return ;
  } 
  
  int mid=(l+r)>>1;
  if(tree[root].add || tree[root].mul!=1) updateUp(root,l,r,mid);
  updateMul(lson,L,R,v);
  updateMul(rson,L,R,v);
  tree[root].v=(tree[root<<1].v+tree[root<<1|1].v)%p;
}

ll query(int root,int l,int r,int L,int R){
  
  if(L>r || R<l) return 0;
  if(L<=l && R>=r) return tree[root].v;
  
  int mid=(l+r)>>1;
  if(tree[root].add || tree[root].mul!=1) updateUp(root,l,r,mid);
  return (query(lson,L,R)+query(rson,L,R))%p;
}

int main(){
  
  scanf("%d%d%lld",&n,&m,&p);
  for(int i=1;i<=n;i++) scanf("%lld",&ans[i]);
  build(1,1,n);
  while(m--){
    
    int type,l,r;
    ll v;
    scanf("%d",&type);
    if(type==1){
      
      scanf("%d%d%lld",&l,&r,&v);
      updateMul(1,1,n,l,r,v);
    }
    else if(type==2){
      
      scanf("%d%d%lld",&l,&r,&v);
      updateAdd(1,1,n,l,r,v);
    }
    else{
      
      scanf("%d%d",&l,&r);
      printf("%lld\n",query(1,1,n,l,r));
    }
  }
}