不懂其他题解在干什么，明明一个线段树就可以做的题偏要各种数据结构一起上，有难写复杂度也不优。介绍一种优质算法。
区间推平区间求和是简单的。现在只需要解决区间向下取整的除法。
对于这种不好直接在线段树上搞得操作，性质又很妙妙的，考虑势能分析。
若区间最大值和最小值除以 \(x\) 的值一样就一起打推平标记即可，其余情况递归即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e6+3;
ll n,m,a[N],sum[N],tag[N],mx[N],mn[N];
#define ls (p<<1)
#define rs (p<<1|1)
#define mi (l+r>>1)
void Up(int p){sum[p]=sum[ls]+sum[rs];mx[p]=max(mx[ls],mx[rs]);mn[p]=min(mn[ls],mn[rs]);}
void Build(int p,int l,int r)
{
tag[p]=-1;
if(l==r){sum[p]=mx[p]=mn[p]=a[l];return;}
Build(ls,l,mi);Build(rs,mi+1,r);
Up(p);
}
void Add(int p,int l,int r,ll d){tag[p]=mx[p]=mn[p]=d;sum[p]=d*(r-l+1);}
void Down(int p,int l,int r)
{
if(tag[p]==-1)return;
Add(ls,l,mi,tag[p]);Add(rs,mi+1,r,tag[p]);tag[p]=-1;
}
void Upd(int L,int R,int p,int l,int r,ll d)
{
if(L<=l&&r<=R&&mx[p]/d==mn[p]/d){Add(p,l,r,mx[p]/d);return;}
Down(p,l,r);
if(L<=mi)Upd(L,R,ls,l,mi,d);
if(R>mi)Upd(L,R,rs,mi+1,r,d);
Up(p);
}
void Mdf(int L,int R,int p,int l,int r,ll d)
{
if(L<=l&&r<=R){Add(p,l,r,d);return;}
Down(p,l,r);
if(L<=mi)Mdf(L,R,ls,l,mi,d);
if(R>mi)Mdf(L,R,rs,mi+1,r,d);
Up(p);
}
ll Query(int L,int R,int p,int l,int r)
{
if(L<=l&&r<=R)return sum[p];
Down(p,l,r);ll s=0;
if(L<=mi)s+=Query(L,R,ls,l,mi);
if(R>mi)s+=Query(L,R,rs,mi+1,r);
return s;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
Build(1,1,n);
while(m--)
{
ll o,l,r,d;cin>>o>>l>>r;
if(o==1)cin>>d,Upd(l,r,1,1,n,d);
if(o==2)cin>>d,Mdf(l,r,1,1,n,d);
if(o==3)cout<<Query(l,r,1,1,n)<<endl;
}
}