sol ：线段树..........蜜汁TLE了一个点，不管了.....
代码抄snowMyDream的，orz...........
线段树需要维护以下奇奇怪怪的一堆东西......
区间最小值及其lazy标记
区间严格次小值及其lazy标记
最小值、严格次小值lazy标记的前缀和，历史最小值
dalao的博客说了一堆势能之类的东西我也没看懂.......我是看代码才明白的QAQ
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define inf 2147483647
using namespace std;
const int Mx=;
int n,m,root,a[Mx],l[Mx],r[Mx];
int tot,lson[Mx],rson[Mx],val[Mx],lazy[Mx],sum[Mx],Mnhis[Mx];
int Val[Mx],Lazy[Mx],Sum[Mx];//次小值 inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }
while(ch>=''&&ch<='') { x=x*+ch-''; ch=getchar(); }
return x*f;
} void pushup(int x)
{
int L=lson[x],R=rson[x];
Mnhis[x]=min(Mnhis[L],Mnhis[R]);
val[x]=min(val[L],val[R]);
if(val[L]!=val[R])
Val[x]=min(max(val[L],val[R]),min(Val[L],Val[R]));
else
Val[x]=min(Val[L],Val[R]);
} void build(int &x,int L,int R)
{
x=++tot,l[x]=L,r[x]=R;
if(L==R)
val[x]=a[L],Val[x]=inf,Mnhis[x]=val[x];
else
{
int mid=(L+R)/;
build(lson[x],L,mid);
build(rson[x],mid+,R);
pushup(x);
}
} void Push(int x,int i,bool flag)
{
int la=lazy[i],La=Lazy[i],su=sum[i],Su=Sum[i];
if(!flag) la=La,su=Su;
Mnhis[x]=min(Mnhis[x],val[x]+su);
val[x]+=la; if(Val[x]!=inf) Val[x]+=La;
sum[x]=min(sum[x],lazy[x]+su),Sum[x]=min(Sum[x],Lazy[x]+Su);
lazy[x]+=la,Lazy[x]+=La;
} void pushdown(int x)
{
if(!lazy[x]&&!Lazy[x]&&sum[x]>=&&Sum[x]>=) return ;
int L=lson[x],R=rson[x];
if(val[L]==val[R]) Push(L,x,),Push(R,x,);
if(val[L]<val[R]) Push(L,x,),Push(R,x,);
if(val[L]>val[R]) Push(L,x,),Push(R,x,);
lazy[x]=Lazy[x]=sum[x]=Sum[x]=;
} void Add(int x,int ll,int rr,int c)
{
int L=l[x],R=r[x];
if(L>rr||R<ll) return ;
if(ll<=L&&rr>=R)
{
val[x]+=c; if(Val[x]!=inf) Val[x]+=c;
lazy[x]+=c,Lazy[x]+=c;
sum[x]=min(sum[x],lazy[x]),Sum[x]=min(Sum[x],Lazy[x]);
Mnhis[x]=min(Mnhis[x],val[x]);
}
else
{
pushdown(x);
Add(lson[x],ll,rr,c);
Add(rson[x],ll,rr,c);
pushup(x);
}
} void Max(int x,int ll,int rr,int c)
{
int L=l[x],R=r[x];
if(L>rr||R<ll) return ;
if(ll<=L&&rr>=R&&Val[x]>c)
{
if(val[x]<c)
{
lazy[x]+=c-val[x];
val[x]=c;
}
}
else
{
pushdown(x);
Max(lson[x],ll,rr,c);
Max(rson[x],ll,rr,c);
pushup(x);
}
} int Query(int x,int ll,int rr,bool flag)
{
int L=l[x],R=r[x];
if(L>rr||R<ll) return inf;
if(ll<=L&&rr>=R)
{
if(flag) return Mnhis[x];
else return val[x];
}
else
{
pushdown(x);
int ans=min(Query(lson[x],ll,rr,flag),Query(rson[x],ll,rr,flag));
pushup(x);
return ans;
}
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) a[i]=read();;
build(root,,n);
for(int i=,num,x,y,z;i<=m;i++)
{
scanf("%d%d%d",&num,&x,&y);
if(num==) z=read(),Add(root,x,y,z);
if(num==) z=read(),Max(root,x,y,z);
if(num==) printf("%d\n",Query(root,x,y,));
if(num==) printf("%d\n",Query(root,x,y,));
}
return ;
}