This repository has been archived by the owner on Jul 16, 2024. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathCF438D.cpp
executable file
·128 lines (127 loc) · 2.46 KB
/
CF438D.cpp
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
// Fear cuts deeper than swords.
#include <math.h>
#include <stdio.h>
using namespace std;
int n, m, k, l;
long long r, x;
long long a[100007];
struct node
{
long long sum;
long long max;
} d[400007];
long long max(long long a, long long b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
void build(int c, int cl, int cr)
{
if (cl == cr)
{
d[c].sum = a[cl];
d[c].max = a[cl];
return;
}
int cm = (cl + cr) >> 1;
build(c << 1, cl, cm);
build((c << 1) | 1, cm + 1, cr);
d[c].sum = d[c << 1].sum + d[(c << 1) | 1].sum;
d[c].max = max(d[c << 1].max, d[(c << 1) | 1].max);
}
long long asksum(int c, int l, int r, int cl, int cr)
{
if (l <= cl && cr <= r)
{
return d[c].sum;
}
int cm = (cl + cr) >> 1;
long long s = 0;
if (l <= cm)
{
s += asksum(c << 1, l, r, cl, cm);
}
if (cm < r)
{
s += asksum((c << 1) | 1, l, r, cm + 1, cr);
}
return s;
}
void rmod(int c, int l, int r, int cl, int cr, long long x)
{
if (d[c].max < x)
{
return;
}
if (cl == cr)
{
d[c].sum = d[c].sum % x;
d[c].max = d[c].sum;
return;
}
int cm = (cl + cr) >> 1;
if (l <= cm)
{
rmod(c << 1, l, r, cl, cm, x);
}
if (cm < r)
{
rmod((c << 1) | 1, l, r, cm + 1, cr, x);
}
d[c].sum = d[c << 1].sum + d[(c << 1) | 1].sum;
d[c].max = max(d[c << 1].max, d[(c << 1) | 1].max);
}
void change(int c, int k, int cl, int cr, long long x)
{
if (cl == cr)
{
d[c].sum = x;
d[c].max = d[c].sum;
return;
}
int cm = (cl + cr) >> 1;
if (k <= cm)
{
change(c << 1, k, cl, cm, x);
}
else
{
change((c << 1) | 1, k, cm + 1, cr, x);
}
d[c].sum = d[c << 1].sum + d[(c << 1) | 1].sum;
d[c].max = max(d[c << 1].max, d[(c << 1) | 1].max);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
}
build(1, 1, n);
for (int i = 1; i <= m; i++)
{
scanf("%d", &k);
if (k == 1)
{
scanf("%d%lld", &l, &r);
printf("%lld\n", asksum(1, l, r, 1, n));
}
else if (k == 2)
{
scanf("%d%lld%lld", &l, &r, &x);
rmod(1, l, r, 1, n, x);
}
else
{
scanf("%d%lld", &l, &r);
change(1, l, 1, n, r);
}
}
}