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
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110000;
int A[N<<2], sum[N<<2];
int B[N<<2], size[N<<2];
int n, m, mo;
void change(int k1){
sum[k1] = (sum[k1*2]+sum[k1*2+1]) % mo;
}
void add(int k1, int k2){
A[k1] = (A[k1]+k2) % mo;
sum[k1] = (sum[k1]+1ll*size[k1]*k2)%mo;
}
void buildtree(int k1, int l, int r){
size[k1] = r-l+1; B[k1] = 1;
if(l == r){
scanf("%d", &sum[k1]);return;
}
int mid = l+r >> 1;
buildtree(k1*2, l, mid);
buildtree(k1*2+1, mid+1, r);
change(k1);
}
void chen(int k1, int k2){
A[k1] = 1ll*A[k1]*k2%mo;
B[k1] = 1ll*B[k1]*k2%mo;
sum[k1] = 1ll*sum[k1]*k2%mo;
}
void pushdown(int k1){
if(B[k1] != 1){
chen(k1*2, B[k1]);
chen(k1*2+1, B[k1]);
B[k1] = 1;
}
if(A[k1]){
add(k1*2, A[k1]);
add(k1*2+1, A[k1]);
A[k1] = 0;
}
}
void add(int k1, int L, int R, int l, int r, int val){
if(L>r || R < l) return;
if(L>=l && R<=r) {
add(k1, val); return;
}
int mid = L+R >> 1;
pushdown(k1);
add(k1*2, L, mid, l, r, val);
add(k1*2+1, mid+1, R, l, r, val);
change(k1);
}
int find(int k1, int L, int R, int l, int r){
if(L>r || R < l) return 0;
if(L>=l && R<=r) return sum[k1];
int mid = L+R>>1; pushdown(k1);
return (find(k1*2, L, mid, l, r) + find(k1*2+1, mid+1, R, l, r))%mo;
}
void chen(int k1, int L, int R, int l, int r, int val){
if(L > r || R < l) return;
if(L>=l && R <= r){
chen(k1, val); return;
}
int mid = L+R >> 1;
pushdown(k1);
chen(k1*2, L, mid, l, r, val);
chen(k1*2+1, mid+1, R, l, r, val);
change(k1);
}
int main(){
cin >> n >> mo;
buildtree(1, 1, n);
int m; cin >> m;
while(m--){
int k1, l, r;
scanf("%d%d%d", &k1, &l, &r);
if(k1 == 2){
int k4;
scanf("%d", &k4);
add(1, 1, n, l, r, k4);
}else if(k1 == 1){
int k4;
scanf("%d", &k4);
chen(1, 1, n, l, r, k4);
}else{
printf("%d\n", find(1, 1, n, l, r));
}
}
return 0;
}
|
