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
| const int N = 200005,V = 1e18;
int a[N];
int n,m;
class segtree{
private:
int tr[N*4];
unsigned s[N*4];
void pushup(int u){
if(tr[u<<1]>V||tr[u<<1|1]>V)
tr[u] = V+1;
else
tr[u] = tr[u<<1]/gcd(tr[u<<1],tr[u<<1|1])*tr[u<<1|1];
s[u] = s[u<<1]+s[u<<1|1];
}
public:
void modify(int u,int l,int r,int L,int R,int v){
if(tr[u]<=V&&v%tr[u]==0)
return;
if(l==r){
s[u] = tr[u] = gcd(tr[u],v);
return;
}
int mid = (l+r)>>1;
if(L<=mid)
modify(u<<1,l,mid,L,R,v);
if(R>mid)
modify(u<<1|1,mid+1,r,L,R,v);
pushup(u);
}
unsigned query(int u,int l,int r,int L,int R){
if(l>=L&&r<=R)
return s[u];
int mid = (l+r)>>1;
if(L<=mid&&R>mid)
return query(u<<1,l,mid,L,R)+query(u<<1|1,mid+1,r,L,R);
if(L<=mid)
return query(u<<1,l,mid,L,R);
return query(u<<1|1,mid+1,r,L,R);
}
void build(int u,int l,int r){
if(l==r){
s[u] = tr[u] = a[l];
return;
}
int mid = (l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
}
}tr;
signed main(){
n = in,m = in;
for(int k=1;k<=n;k++)
a[k] = in;
tr.build(1,1,n);
while(m--){
int op = in,l = in,r = in;
if(op==1)
tr.modify(1,1,n,l,r,in);
else
out(tr.query(1,1,n,l,r),'\n');
}
return 0;
}
|