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
| #include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r
ll read(){ll r;scanf("%lld",&r);return r;}
using A3=std::array<ll,3>;
A3 seg[2'000'010];
ll a[500'010];
void down(int o,int l,int r){
assert(l!=r);
if(seg[o][1]){
ll v=seg[o][2];
seg[SEG_L]={(mid-l+1)*v,true,v};
seg[SEG_R]={(r-mid)*v,true,v};
}
}
A3 up(int o){
auto [s0,b0,v0]=seg[SEG_L];
auto [s1,b1,v1]=seg[SEG_R];
return seg[o]={s0+s1,b0&&b1&&v0==v1,v0};
}
A3 build(int o,int l,int r){
if(l==r)return seg[o]={a[l],true,a[l]};
build(SEG_L_CHILD);
build(SEG_R_CHILD);
return up(o);
}
A3 div(int o,int l,int r,int ql,int qr,ll x){
if(ql<=l&&r<=qr&&seg[o][1]){
seg[o][2]/=x;
seg[o][0]=(r-l+1)*seg[o][2];
return seg[o];
}
down(o,l,r);
if(ql<=mid) div(SEG_L_CHILD,ql,qr,x);
if(qr> mid) div(SEG_R_CHILD,ql,qr,x);
return up(o);
}
A3 set(int o,int l,int r,int ql,int qr,ll x){
if(ql<=l&&r<=qr) return seg[o]={x*(r-l+1),true,x};
down(o,l,r);
if(ql<=mid) set(SEG_L_CHILD,ql,qr,x);
if(qr> mid) set(SEG_R_CHILD,ql,qr,x);
return up(o);
}
ll sum(int o,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return seg[o][0];
down(o,l,r);
ll ret=0;
if(ql<=mid)ret+=sum(SEG_L_CHILD,ql,qr);
if(qr> mid)ret+=sum(SEG_R_CHILD,ql,qr);
return ret;
}
int main(){
int n=read();
int q=read();
rep(i,0,n)a[i]=read();
build(SEG_ROOT);
while(q--){
int op=read();
int l=read()-1;
int r=read()-1;
if(op==1){
div(SEG_ROOT,l,r,read());
}else if(op==2){
set(SEG_ROOT,l,r,read());
}else{
printf("%lld\n",sum(SEG_ROOT,l,r));
}
}
return 0;
}
|