线段树模板2 洛谷p3373

题目链接：https://www.luogu.com.cn/problem/P3373
本题思路主要也是借鉴了洛谷题解区的方法
通过建立两个标签，tag1用于加法记忆，tag2用于乘法记忆
关键是注意两个运算标签的处理当个简单模板康康
  1 #include<bits/stdc++.h>

  2 #define ll long long
  3 using namespace std;
  4 const int maxn=1e5+10;

  5 int n,w,m;
  6 int temp[4*maxn]; 

  7 struct Segment_Tree
  8 {
  9 ll val;
 10 ll tag1;
 11 ll tag2;
 12 }data[maxn*4];

 13 inline void push_up(int root)
 14 {
 15 　　data[root].val=(data[root<<1].val+data[root<<1|1].val)%m;
 16 }

 17 void build(int left,int right,int root)//root为线段树下标,left为数组下标 
 18 {
 19 　　data[root].tag1=0;
 20 　　data[root].tag2=1;
 21 　　if(left == right){
 22 　　　　data[root].val=temp[left];
 23 　　　　return ;    
 24 　　}
 25 　　int mid=(left+right)>>1;
 26 　　build(left,mid,root<<1);
 27 　　build(mid+1,right,root<<1|1);
 28 　　data[root].val=data[root<<1].val+data[root<<1|1].val;
 29 　　data[root].val%=m; 30 } 31  32 inline void push_down(int left,int right,int root)
 33 {
 34 　　int mid=(left+right)>>1;
 35 　　data[root<<1].val=(data[root<<1].val*data[root].tag2+(mid-left+1)*data[root].tag1)%m;
 36 　　data[root<<1|1].val=(data[root<<1|1].val*data[root].tag2+(right-mid)*data[root].tag1)%m;
 37 　　data[root<<1].tag2=(data[root].tag2*data[root<<1].tag2)%m;
 38 　　data[root<<1|1].tag2=(data[root].tag2*data[root<<1|1].tag2)%m;
 39 　　data[root<<1].tag1=(data[root<<1].tag1*data[root].tag2+data[root].tag1)%m;
 40 　　data[root<<1|1].tag1=(data[root<<1|1].tag1*data[root].tag2+data[root].tag1)%m;
 41 　　data[root].tag1=0;
 42 　　data[root].tag2=1; 
 43 }

 44 void add(int left,int right,int root,int x,int y,int v)
 45 {
 46 　　if(x > right || y < left)    return ;
 47 　　if(x <= left && y >= right){//注意符号
 48 　　　　data[root].val=(data[root].val+(right-left+1)*v)%m;
 49 　　　　data[root].tag1=(data[root].tag1+v)%m;
 50 　　　　return ;
 51 　　}
 52 　　push_down(left,right,root);
 53 　　int mid=(left+right)>>1;
 54 　　add(left,mid,root<<1,x,y,v);
 55 　　add(mid+1,right,root<<1|1,x,y,v);
 56 　　push_up(root);//
 57 }

 58 void multiply(int left,int right,int root,int x,int y,int v)
 59 {
 60 　　if(x > right || y < left)    return ;
 61 　　if(x <= left && y >= right){
 62 　　　　data[root].val=(data[root].val*v)%m;
 63 　　　　data[root].tag2=(data[root].tag2*v)%m;
 64 　　　　data[root].tag1=(data[root].tag1*v)%m;//加的也要乘 
 65 　　　　return ;
 66 　　}
 67 　　push_down(left,right,root);
 68 　　int mid=(left+right)>>1;
 69 　　multiply(left,mid,root<<1,x,y,v);
 70 　　multiply(mid+1,right,root<<1|1,x,y,v);
 71 　　push_up(root);
 72 }

 73 ll query(int left,int right,int root,int x,int y)
 74 {
 75 　　if(x > right || y < left)    return 0;
 76 　　if(x <= left && y >= right){
 77 　　　　return data[root].val;
 78 　　}
 79 　　int mid=(left+right)>>1;
 80 　　push_down(left,right,root);
 81 　　return (query(left,mid,root<<1,x,y)+query(mid+1,right,root<<1|1,x,y))%m;
 82 }

 83 int main(){
 84 　　cin >> n >> w >> m;
 85 　　for(int i = 1 ; i <= n ; i++){
 86 　　　　cin >> temp[i];
 87 　　}
 88 　　build(1,n,1);
 89 　　int flag,a,b,v;
 90 　　for(int i = 1 ; i <= w ; i++){
 91 　　　　scanf("%d",&flag);
 92 　　　　if(flag == 1){
 93 　　　　　　scanf("%d%d%d",&a,&b,&v);
 94 　　　　　　multiply(1,n,1,a,b,v);
 95 　　　　}else if(flag == 2){
 96 　　　　　　scanf("%d%d%d",&a,&b,&v);
 97 　　　　　　add(1,n,1,a,b,v);
 98 　　　　}else{
 99 　　　　　　scanf("%d%d",&a,&b);
100 　　　　　　printf("%lld
",query(1,n,1,a,b)%m);
101　　　　 }
102 　　}
103 　　return 0;
104 }
105 
106