OI

【线段树】维护序列、线段树模板2

P2023 ANOI2009、P3373基本是同一题（

首先，一个节点里分别存加法和乘法两个lazytag。关键问题是乘法运算和加法运算的优先级问题。
因为乘法有分配率，所以一次乘法后加法的lazytag也要乘上一次。对于每个节点的操作，最终可以表示为：

设加法lazytag=d
乘法lazytag=k
节点的值=a
节点区间长=n
则a’=n*d+ka
由此确定对lazytag的处理顺序。
最后，乘法和加法可以自由取模：
(a+b)%c=(a%c+b%c)%c
(a*b)%c=(a%c)(b%c)%c 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<stdio.h>
#include<stdlib.h>
#define MAX 100005
typedef long long ll;

struct node{
    ll val,tadd,tmul;
};
struct node segtree[MAX*4];
ll a[MAX];
int MOD;

void build(int rt,int st,int ed){
    segtree[rt].tadd=0;
    segtree[rt].tmul=1;
    if(st==ed){
        segtree[rt].val=a[st];
        return;
    }
    int mid=(st+ed)>>1;
    build(rt<<1,st,mid);
    build(rt<<1|1,mid+1,ed);
    segtree[rt].val=(segtree[rt<<1].val+segtree[rt<<1|1].val)%MOD;
}

void push(int rt,int st,int ed){
    if(segtree[rt].tmul!=1){//mul first
        segtree[rt<<1].tmul*=segtree[rt].tmul;
        segtree[rt<<1].tmul%=MOD;
        segtree[rt<<1].tadd*=segtree[rt].tmul;
        segtree[rt<<1].tadd%=MOD;
        segtree[rt<<1|1].tmul*=segtree[rt].tmul;
        segtree[rt<<1|1].tmul%=MOD;
        segtree[rt<<1|1].tadd*=segtree[rt].tmul;
        segtree[rt<<1|1].tadd%=MOD;
        
        segtree[rt<<1].val*=segtree[rt].tmul;
        segtree[rt<<1].val%=MOD;
        segtree[rt<<1|1].val*=segtree[rt].tmul;
        segtree[rt<<1|1].val%=MOD;
        
        segtree[rt].tmul=1;
    }
    if(segtree[rt].tadd!=0){//add then
        segtree[rt<<1].tadd+=segtree[rt].tadd;
        segtree[rt<<1].tadd%=MOD;
        segtree[rt<<1|1].tadd+=segtree[rt].tadd;
        segtree[rt<<1|1].tadd%=MOD;
        
        int mid=(st+ed)>>1;
        segtree[rt<<1].val+=segtree[rt].tadd*(mid-st+1)%MOD;
        segtree[rt<<1].val%=MOD;
        segtree[rt<<1|1].val+=segtree[rt].tadd*(ed-mid)%MOD;
        segtree[rt<<1|1].val%=MOD;
        segtree[rt].tadd=0;
    }
}

ll query(int rt,int nst,int ned,int qst,int qed){
    if(qst>ned||qed<nst)
      return 0;
    if(qst<=nst&&qed>=ned)
      return segtree[rt].val;
    push(rt,nst,ned);
    int mid=(nst+ned)>>1;
    return (query(rt<<1,nst,mid,qst,qed)+query(rt<<1|1,mid+1,ned,qst,qed))%MOD;
}

void add(int rt,int nst,int ned,int ust,int ued,int val){
    if(ust>ned||ued<nst)
      return;
    if(ust<=nst&&ued>=ned){
        segtree[rt].tadd+=val%MOD;
        segtree[rt].tadd%=MOD;
        segtree[rt].val+=val*(ned-nst+1)%MOD;
        segtree[rt].val%=MOD;
        return;
    }
    push(rt,nst,ned);
    int mid=(nst+ned)>>1;
    add(rt<<1,nst,mid,ust,ued,val);
    add(rt<<1|1,mid+1,ned,ust,ued,val);
    segtree[rt].val=(segtree[rt<<1].val+segtree[rt<<1|1].val)%MOD;
}

void mul(int rt,int nst,int ned,int ust,int ued,int val){
    if(ust>ned||ued<nst)
      return;
    if(ust<=nst&&ued>=ned){
        segtree[rt].tmul*=val%MOD;
        segtree[rt].tmul%=MOD;
        segtree[rt].tadd*=val%MOD;
        segtree[rt].tadd%=MOD;
        segtree[rt].val*=val%MOD;
        segtree[rt].val%=MOD;
        return;
    }
    push(rt,nst,ned);
    int mid=(nst+ned)>>1;
    mul(rt<<1,nst,mid,ust,ued,val);
    mul(rt<<1|1,mid+1,ned,ust,ued,val);
    segtree[rt].val=(segtree[rt<<1].val+segtree[rt<<1|1].val)%MOD;
}

int main(){
    int n,m,i,type,t,g,c;
    scanf("%d%d",&n,&MOD);
    for(i=1;i<=n;i++)
      scanf("%lld",&a[i]);
      
    build(1,1,n);
    
    //for(i=1;i<=20;i++)
    //  printf("%lld ",segtree[i].val);
      
    //printf("\n%lld\n",query(1,1,n,2,5));
    
    scanf("%d",&m);
    for(i=1;i<=m;i++){
        scanf("%d",&type);
        if(type==1){
            scanf("%d%d%d",&t,&g,&c);
            mul(1,1,n,t,g,c);
            
        }
        else if(type==2){
            scanf("%d%d%d",&t,&g,&c);
            add(1,1,n,t,g,c);
        }
        else{
            scanf("%d%d",&t,&g);
            printf("%lld\n",query(1,1,n,t,g));
        }
    }
    return 0;
}