老师说，你们暴力求除法也整不了多少次就归一了，暴力就好了（应该只有log（n）次）
于是暴力啊暴力，结果我归天了。
好吧，在各种题解的摧残下，我终于出了一篇巨好看（chou lou）代码（很多结构体党嫌丑）
那么具体除法怎么实现就是关键了
对于单个点或者区间内的数完全相同的区间，可以做成区间减法
因为除法会使数变小，而相同的数减小的量是相同的，
那么怎么判断区间内的数是否完全相同呢？
可以维护一个区间最小与区间最大，如果一个区间内最小数等于最大数，那么显然这个区间内所有数相等
区间最小与区间最大就不用说了吧？
然后暴力一波
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll sum[400101]={0}, minn[400101],maxx[400001]={0},add[400101]={0},a[401001];
int n,m;
void pushup(ll rt){
sum[rt]=sum[rt<<1|1]+sum[rt<<1];
minn[rt]=min(minn[rt<<1],minn[rt<<1|1]);
maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]);
}
inline ll Div(ll x, ll y) {//从样例分析出这道题是向下取整的除法
return floor((double)x/y);
}
void build(ll l,ll r,ll rt){
if(l==r){
sum[rt]=a[l];
minn[rt]=a[l];
maxx[rt]=a[l];
return ;
}
long long mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void pushdown(ll rt,ll ln,ll rn){
if(add[rt]!=0){
add[rt<<1]+=add[rt];
add[rt<<1|1]+=add[rt];
sum[rt<<1]+=add[rt]*ln;
sum[rt<<1|1]+=add[rt]*rn;
minn[rt<<1]+=add[rt];
minn[rt<<1|1]+=add[rt];
maxx[rt<<1]+=add[rt];
maxx[rt<<1|1]+=add[rt];
add[rt]=0;
}
}
void update1(ll l,ll r,ll c,ll L,ll R,ll rt){
if(l>=L&&r<=R){
sum[rt]+=c*(r-l+1);
add[rt]+=c;minn[rt]+=c;maxx[rt]+=c;
return ;
}
ll mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid)update1(l,mid,c,L,R,rt<<1);
if(R>mid)update1(mid+1,r,c,L,R,rt<<1|1);
pushup(rt);
}
void update2(ll l,ll r,ll c,ll L,ll R,ll rt){//对于除法的暴力操作
if (l >=L&&r<=R&&maxx[rt]-Div(maxx[rt],c)==minn[rt]-Div(minn[rt],c)){
ll D=Div(maxx[rt],c)-maxx[rt];
add[rt]+=D;maxx[rt]+=D;minn[rt]+=D;
sum[rt]+=D*(r-l+1);
return;
}
ll mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid)update2(l,mid,c,L,R,rt<<1);
if(mid<R)update2(mid+1,r,c,L,R,rt<<1|1);
pushup(rt);
}
ll query1(ll l,ll r,ll L,ll R,ll rt){
if(l>=L&&r<=R){
return sum[rt];
}
ll mid=(l+r)>>1;
ll ans=0;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid)ans+=query1(l,mid,L,R,rt<<1);
if(R>mid)ans+=query1(mid+1,r,L,R,rt<<1|1);
return ans;
}
ll query2(ll l,ll r,ll L,ll R,ll rt){
if(l>=L&&r<=R){
return minn[rt];
}
ll mid=(l+r)>>1;
ll ans=1e18;
pushdown(rt,mid-l+1,r-mid);
if(L<=mid)ans=min(ans,query2(l,mid,L,R,rt<<1));
if(R>mid)ans=min(ans,query2(mid+1,r,L,R,rt<<1|1));
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
//memset(flag,1,sizeof(flag));
build(0,n-1,1);
while(m--){
long long c,x,y,k;
scanf("%lld%lld%lld",&c,&x,&y);
if(c==1){scanf("%lld",&k);update1(0,n-1,k,x,y,1);}
if(c==2){scanf("%lld",&k);update2(0,n-1,k,x,y,1);}
if(c==4)printf("%lld
",query1(0,n-1,x,y,1));
if(c==3)printf("%lld
",query2(0,n-1,x,y,1));
}
return 0;
}