分析
就是线段树啊
至于除法就记录区间minmax看是不是相当于区间减即可
复杂度不会证明
就上网查根号势能分析把根号改成1/k就行啦
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e17+9;
int mn[400100],mx[400100],d[400100],n,m,a[100100],col[400100];
inline void build(int le,int ri,int wh){
if(le==ri){d[wh]=mn[wh]=mx[wh]=a[le];return;}
int mid=(le+ri)>>1;
build(le,mid,wh<<1),build(mid+1,ri,wh<<1|1);d[wh]=d[wh<<1]+d[wh<<1|1];
mn[wh]=min(mn[wh<<1],mn[wh<<1|1]);mx[wh]=max(mx[wh<<1],mx[wh<<1|1]);
}
inline void pushdown(int wh,int le,int mid,int ri){
if(!col[wh])return;
int k=col[wh];
d[wh<<1]+=(mid-le+1)*k;
d[wh<<1|1]+=(ri-mid)*k;
mn[wh<<1]+=k,mn[wh<<1|1]+=k;
mx[wh<<1]+=k,mx[wh<<1|1]+=k;
col[wh<<1]+=k,col[wh<<1|1]+=k;
col[wh]=0;
}
inline int qmin(int le,int ri,int wh,int x,int y){
if(le>=x&&ri<=y)return mn[wh];
int mid=(le+ri)>>1,ans=inf;
pushdown(wh,le,mid,ri);
if(mid>=x)ans=min(ans,qmin(le,mid,wh<<1,x,y));
if(mid<y)ans=min(ans,qmin(mid+1,ri,wh<<1|1,x,y));
return ans;
}
inline int qsum(int le,int ri,int wh,int x,int y){
if(le>=x&&ri<=y)return d[wh];
int mid=(le+ri)>>1,ans=0;
pushdown(wh,le,mid,ri);
if(mid>=x)ans+=qsum(le,mid,wh<<1,x,y);
if(mid<y)ans+=qsum(mid+1,ri,wh<<1|1,x,y);
return ans;
}
inline void update(int le,int ri,int wh,int x,int y,int k){
if(le>=x&&ri<=y){
col[wh]+=k;
mn[wh]+=k;
mx[wh]+=k;
d[wh]+=k*(ri-le+1);
return;
}
int mid=(le+ri)>>1;
pushdown(wh,le,mid,ri);
if(mid>=x)update(le,mid,wh<<1,x,y,k);
if(mid<y)update(mid+1,ri,wh<<1|1,x,y,k);
mn[wh]=min(mn[wh<<1],mn[wh<<1|1]);
mx[wh]=max(mx[wh<<1],mx[wh<<1|1]);
d[wh]=d[wh<<1]+d[wh<<1|1];
return;
}
inline int getdiv(int x,int y){return x>=0?x/y:((x+1)/y-1);}
inline void updiv(int le,int ri,int wh,int x,int y,int k){
if(le>=x&&ri<=y&&(mx[wh]-getdiv(mx[wh],k)==mn[wh]-getdiv(mn[wh],k))){
int a=mx[wh]-getdiv(mx[wh],k);
col[wh]-=a;
mn[wh]-=a;
mx[wh]-=a;
d[wh]-=a*(ri-le+1);
return;
}
int mid=(le+ri)>>1;
pushdown(wh,le,mid,ri);
if(mid>=x)updiv(le,mid,wh<<1,x,y,k);
if(mid<y)updiv(mid+1,ri,wh<<1|1,x,y,k);
mn[wh]=min(mn[wh<<1],mn[wh<<1|1]);
mx[wh]=max(mx[wh<<1],mx[wh<<1|1]);
d[wh]=d[wh<<1]+d[wh<<1|1];
return;
}
signed main(){
int i,j,k,le,ri,x;
cin>>n>>m;
for(i=1;i<=n;i++)scanf("%lld",&a[i]);
build(1,n,1);
while(m--){
scanf("%lld%lld%lld",&k,&le,&ri);
le++,ri++;
if(k==1||k==2)scanf("%lld",&x);
if(k==1)update(1,n,1,le,ri,x);
if(k==2)updiv(1,n,1,le,ri,x);
if(k==3)printf("%lld\n",qmin(1,n,1,le,ri));
if(k==4)printf("%lld\n",qsum(1,n,1,le,ri));
}
return 0;
}