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
|
#include <cstdio>
#define int long long
#define re register
#define mid ((l + r) / 2)
using namespace std;
const int N = 500000;
int n, m, p, opt, x, y, k;
int a[N], sum[N], mul[N], add[N];
inline int ()
{
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
return f * x;
}
void push_up(int x) { sum[x] = (sum[x * 2] + sum[x * 2 + 1]) % p; }
void push_down(int x, int l, int r)
{
mul[x * 2] = (mul[x * 2] * mul[x]) % p;
mul[x * 2 + 1] = (mul[x * 2 + 1] * mul[x]) % p;
add[x * 2] = (add[x * 2] * mul[x] + add[x]) % p;
add[x * 2 + 1] = (add[x * 2 + 1] * mul[x] + add[x]) % p;
sum[x * 2] = (sum[x * 2] * mul[x] + add[x] * (mid - l + 1)) % p;
sum[x * 2 + 1] = (sum[x * 2 + 1] * mul[x] + add[x] * (r - mid)) % p;
mul[x] = 1, add[x] = 0;
push_up(x);
}
void build(int x, int l, int r)
{
mul[x] = 1, add[x] = 0;
if(l == r)
{
sum[x] = a[l];
return ;
}
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
push_up(x);
}
void upd_mul(int x, int l, int r, int stdl, int stdr, int k)
{
if(stdl <= l && stdr >= r)
{
mul[x] = (mul[x] * k) % p, add[x] = (add[x] * k) % p;
sum[x] = (sum[x] * k) % p;
return ;
}
if(stdl > r || stdr < l) return ;
push_down(x, l, r);
upd_mul(x * 2, l, mid, stdl, stdr, k);
upd_mul(x * 2 + 1, mid + 1, r, stdl, stdr, k);
push_up(x);
}
void upd_add(int x, int l, int r, int stdl, int stdr, int k)
{
if(stdl <= l && stdr >= r)
{
add[x] = (add[x] + k) % p;
sum[x] = (sum[x] + (r - l + 1) * k);
return ;
}
if(stdl > r || stdr < l) return ;
push_down(x, l, r);
upd_add(x * 2, l, mid, stdl, stdr, k);
upd_add(x * 2 + 1, mid + 1, r, stdl, stdr, k);
push_up(x);
}
int query(int x, int l, int r, int stdl, int stdr)
{
if(stdl <= l && stdr >= r) return sum[x] % p;
if(stdl > r || stdr < l) return 0;
push_down(x, l, r);
return (query(x * 2, l, mid, stdl, stdr) + query(x * 2 + 1, mid + 1, r, stdl, stdr)) % p;
push_up(x);
}
signed main()
{
n = read(), m = read(), p = read();
for(re int i = 1; i <= n; i++) a[i] = read();
build(1, 1, n);
for(re int i = 1; i <= m; i++)
{
opt = read();
if(opt == 1)
{
x = read(), y = read(), k = read();
upd_mul(1, 1, n, x, y, k);
}
if(opt == 2)
{
x = read(), y = read(), k = read();
upd_add(1, 1, n, x, y, k);
}
if(opt == 3)
{
x = read(), y = read();
printf("%lldn", query(1, 1, n, x, y));
}
}
return 0;
}
|
近期评论