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
| #include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll N = 1e5+5;
ll tree[N<<2];
ll a[N];
ll add[N<<2], mul[N<<2];
ll mod;
ll ls(ll p){
return p*2;
}
ll rs(ll p){
return p * 2 + 1;
}
void push_up(ll p){
tree[p] = (tree[ls(p)] + tree[rs(p)]) % mod;
}
void push_down(ll p, ll pl, ll pr){
ll mid = (pl+pr)/2;
tree[ls(p)] = (mul[p] * tree[ls(p)] + add[p] * (mid - pl + 1)) % mod;
tree[rs(p)] = (mul[p] * tree[rs(p)] + add[p] * (pr - mid)) % mod;
mul[ls(p)] = (mul[ls(p)] * mul[p]) % mod;
mul[rs(p)] = (mul[rs(p)] * mul[p]) % mod;
add[ls(p)] = (add[ls(p)] * mul[p] + add[p]) % mod;
add[rs(p)] = (add[rs(p)] * mul[p] + add[p]) % mod;
mul[p] = 1;
add[p] = 0;
}
void ChangeAdd(ll p, ll pl, ll pr, ll l, ll r, ll k){
if(l <= pl && r >= pr){
add[p] = (add[p] + k) % mod;
tree[p] = (tree[p] + k * (pr - pl + 1)) % mod;
return;
}
push_down(p, pl, pr);
ll mid = (pl + pr)/2;
if(l <= mid) ChangeAdd(ls(p), pl, mid, l, r, k);
if(r > mid) ChangeAdd(rs(p), mid + 1, pr, l, r, k);
push_up(p);
return;
}
void ChangeMul(ll p, ll pl, ll pr, ll l, ll r, ll k){
if(l <= pl && r >= pr){
add[p] = (add[p] * k) % mod;
mul[p] = (mul[p] * k) % mod;
tree[p] = (tree[p] * k) % mod;
return;
}
push_down(p, pl, pr);
ll mid = (pl + pr)/2;
if(l <= mid) ChangeMul(ls(p), pl, mid, l, r, k);
if(r > mid) ChangeMul(rs(p), mid + 1, pr, l, r, k);
push_up(p);
return;
}
void build(ll p, ll pl, ll pr){
add[p] = 0, mul[p] = 1;
if(pl == pr){
tree[p] = a[pl] % mod;
return;
}
ll mid = (pl + pr)/2;
build(ls(p), pl, mid);
build(rs(p), mid + 1, pr);
push_up(p);
}
ll query(ll p, ll pl, ll pr, ll l, ll r){
if(l <= pl && r >= pr) return tree[p];
push_down(p, pl, pr);
ll val = 0;
ll mid = (pl + pr)/2;
if(l <= mid) val = (val + query(ls(p), pl, mid, l, r)) % mod;
if(r > mid) val = (val + query(rs(p), mid + 1, pr, l, r)) % mod;
return val;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll n,q;
cin>>n>>q>>mod;
for(int i = 1; i <= n; i++){
cin>>a[i];
}
build(1, 1, n);
while(q--){
int jud;
cin>>jud;
if(jud == 3){
ll l,r;
cin>>l>>r;
cout<<query(1, 1, n, l, r)<<endl;
}else if(jud == 2){
ll l,r,k;
cin>>l>>r>>k;
ChangeAdd(1, 1, n, l, r, k);
}else{
ll l,r,k;
cin>>l>>r>>k;
ChangeMul(1, 1, n, l, r, k);
}
}
return 0;
}
|
支付宝
微信