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
| #include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define MS 100009
#define INF 20000009
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
LL mod;
LL n,m,k;
LL p[MS<<2];
LL la_add[MS<<2];
LL la_mul[MS<<2];
void init(int l,int r,int rt){
if(l == r){
la_mul[rt] = 1;
return;
}
int m = l+r>>1;
init(l,m,ls);
init(m+1,r,rs);
}
void push_up(int rt){
p[rt] = p[ls] + p[rs];
p[rt] %= mod;
}
void push_down(int rt,int l,int r){
int m = l+r>>1;
p[ls] = (p[ls]*la_mul[rt]+la_add[rt]*(m-l+1))%mod;
p[rs] = (p[rs]*la_mul[rt]+la_add[rt]*(r-m))%mod;
la_mul[ls] = (la_mul[ls]*la_mul[rt])%mod;
la_mul[rs] = (la_mul[rs]*la_mul[rt])%mod;
la_add[ls] = (la_add[ls]*la_mul[rt]+la_add[rt])%mod;
la_add[rs] = (la_add[rs]*la_mul[rt]+la_add[rt])%mod;
la_add[rt] = 0;
la_mul[rt] = 1;
}
void update_add(int L,int R,int l,int r,int rt,LL val){
if(L <= l && r <= R){
p[rt] += (r-l+1)*val;
p[rt] %= mod;
la_add[rt] += val;
la_add[rt] %= mod;
return;
}
push_down(rt,l,r);
int m = l+r>>1;
if(m >= L) update_add(L,R,l,m,ls,val);
if(m < R) update_add(L,R,m+1,r,rs,val);
push_up(rt);
}
void update_mul(int L,int R,int l,int r,int rt,LL val){
if(L <= l && r <= R){
p[rt] *= val;
p[rt] %= mod;
la_mul[rt] *= val;
la_mul[rt] %= mod;
la_add[rt] *= val;
la_add[rt] %= mod;
return;
}
push_down(rt,l,r);
int m = l+r>>1;
if(m >= L) update_mul(L,R,l,m,ls,val);
if(m < R) update_mul(L,R,m+1,r,rs,val);
push_up(rt);
}
LL get_sum(int L,int R,int l,int r,int rt){
if(L <= l && r <= R){
return p[rt]%mod;
}
push_down(rt,l,r);
LL cc = 0;
int m = l+r>>1;
if(m >= L) cc = (cc+get_sum(L,R,l,m,ls))%mod;
if(m < R) cc = (cc+get_sum(L,R,m+1,r,rs))%mod;
return cc%mod;
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> mod;
init(1,n,1);
for(int i=1;i<=n;i++){
LL x;
cin >> x;
update_add(i,i,1,n,1,x%mod);
}
while(m--){
LL op,l,r,val;
cin >> op >> l >> r;
if(op == 1){
cin >> val;
update_mul(l,r,1,n,1,val);
}
else if(op == 2){
cin >> val;
update_add(l,r,1,n,1,val);
}
else{
LL ans = get_sum(l,r,1,n,1);
cout << ans << endl;
}
}
return 0;
}
|
