题意
区间整除，区间推平，查询区间和。
大家好啊，我喜欢暴力乱搞，所以这题我用暴力乱搞 AC 了。
首先观察到操作 \(1\) 的性质：首先保证了除数至少为 \(2\)（不然是 \(1\) 或者 \(0\) 的话也没啥意义啊），所以对一个数不断进行操作的话，每次数的大小至少会减少一半，减小到 \(0\) 之后就不用操作了，因为再操作也就没有意义了，所以最多进行的次数是 \(\log_x\) 级别，其中 \(x\) 是原先的数值。所以我们用线段树维护区间和的同时再维护一个区间最大值，每次只要当前区间的最大值不为 \(0\) 就进去暴力修改，时间复杂度为 \(O(n\log n)\)。
但是有个问题是，如果加上区间推平操作之后，我们每次推平之后就不能维持原来的最大值了，这样最坏复杂度就又会退化成纯暴力的复杂度。
但是区间推平这个操作我们还可以用另一个东西去维护啊，没错就是 \(ODT\)！
但是如果区间推平操作很少的话，\(ODT\) 的用时表现就会变得很差。
所以我们直接合在一起乱搞啊！
将全部操作存下来，同时给区间推平操作计数，如果次数大于 \(2000\) 就用 \(ODT\)，否则就用线段树。
然后你就会发现这东西跑得飞快（。
\(\text{Code:}\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define re register
const int N=500500;
int n,m,a[N],cnt;
struct query{
int op,l,r,x;
}q[N];
il int read(){
re int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
struct Chtholly{
int l,r;
mutable int val;
Chtholly(int l,int r=0,int val=0):l(l),r(r),val(val){}
bool operator<(const Chtholly &a)const{
return l<a.l;
}
};
set<Chtholly>s;
#define It set<Chtholly>::iterator
il It Split(int pos){
It fnd=s.lower_bound(Chtholly(pos));
if(fnd!=s.end()&&fnd->l==pos)return fnd;
fnd--;
if(fnd->r<pos)return s.end();
int l=fnd->l,r=fnd->r,val=fnd->val;
s.erase(fnd);
s.insert(Chtholly(l,pos-1,val));
return s.insert(Chtholly(pos,r,val)).first;
}
il void Assign(int l,int r,int x){
It R=Split(r+1),L=Split(l);
s.erase(L,R);
s.insert(Chtholly(l,r,x));
}
il void update(int l,int r,int x){
It R=Split(r+1),L=Split(l);
for(re It i=L;i!=R;i++)i->val/=x;
}
il void solve(int l,int r){
int res=0;
It R=Split(r+1),L=Split(l);
for(re It i=L;i!=R;i++)
res+=(i->r-i->l+1)*i->val;
printf("%lld\n",res);
}
struct SegmentTree{
int sum,mx,tag;
}L[N<<2];
#define ls (id<<1)
#define rs (id<<1|1)
il void pushup(SegmentTree &fa,SegmentTree lson,SegmentTree rson){
fa.sum=lson.sum+rson.sum;
fa.mx=max(lson.mx,rson.mx);
}
il void pushdown(SegmentTree &fa,SegmentTree &lson,SegmentTree &rson,int l,int r){
if(!fa.tag)return;
int mid=(l+r)>>1,t=fa.tag;
lson={(mid-l+1)*t,t,t};
rson={(r-mid)*t,t,t};
fa.tag=0;
}
il void upd(int id,int l,int r,int x,int y,int z){
if(!L[id].mx)return;
if(l==r){
L[id].sum/=z,L[id].mx/=z;
return;
}
int mid=(l+r)>>1;
pushdown(L[id],L[ls],L[rs],l,r);
if(x<=mid)upd(ls,l,mid,x,y,z);
if(y>mid)upd(rs,mid+1,r,x,y,z);
pushup(L[id],L[ls],L[rs]);
}
il void Ass(int id,int l,int r,int x,int y,int z){
if(l>=x&&r<=y){
L[id]={(r-l+1)*z,z,z};
return;
}
int mid=(l+r)>>1;
pushdown(L[id],L[ls],L[rs],l,r);
if(x<=mid)Ass(ls,l,mid,x,y,z);
if(y>mid)Ass(rs,mid+1,r,x,y,z);
pushup(L[id],L[ls],L[rs]);
}
il int GetSum(int id,int l,int r,int x,int y){
if(l>=x&&r<=y)return L[id].sum;
int mid=(l+r)>>1,res=0;
pushdown(L[id],L[ls],L[rs],l,r);
if(x<=mid)res+=GetSum(ls,l,mid,x,y);
if(y>mid)res+=GetSum(rs,mid+1,r,x,y);
pushup(L[id],L[ls],L[rs]);
return res;
}
il void build(int id,int l,int r){
if(l==r){
L[id]={a[l],a[l],0};
return;
}
int mid=(l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r);
pushup(L[id],L[ls],L[rs]);
}
il void solve_odt(){
for(re int i=1;i<=n;i++)
s.insert(Chtholly(i,i,a[i]));
for(re int i=1;i<=m;i++){
if(q[i].op==1)update(q[i].l,q[i].r,q[i].x);
if(q[i].op==2)Assign(q[i].l,q[i].r,q[i].x);
if(q[i].op==3)solve(q[i].l,q[i].r);
}
}
il void solveSegmentTree(){
build(1,1,n);
for(re int i=1;i<=m;i++){
int op=q[i].op,l=q[i].l,r=q[i].r,x=q[i].x;
if(op==1)upd(1,1,n,l,r,x);
if(op==2)Ass(1,1,n,l,r,x);
if(op==3)printf("%lld\n",GetSum(1,1,n,l,r));
}
}
signed main(){
n=read(),m=read();
for(re int i=1;i<=n;i++)a[i]=read();
for(re int i=1;i<=m;i++){
q[i].op=read(),q[i].l=read(),q[i].r=read();
if(q[i].op!=3)q[i].x=read();
if(q[i].op==2)cnt++;
}
if(cnt>2000)solve_odt();
else solveSegmentTree();
return 0;
}