题解：
线段树维护区间取min求和求max
维护最小值以及个数，次小值
标记清除时，分情况讨论
当lazy>max1 退出
当max1>lazy>max2(注意不要有等号） 更新
否则递归处理
据吉如一的论文上说是nlogn的复杂度（至今不知论文在何处）
卡常？？ 不懂常熟技巧 那就开个o2水一下。。。。
这数的大小 正好2^31 刚开始没看。。对拍挺对交上去wa了
#pragma G++ optimize (2)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1100000
#define INF 2147483647
#define il inline
struct re{
int max1,max2,num,h,t,lazy;
ll sum;
}p[N*];
ll b[N];
int T,n,m;
il void updata(int x)
{
p[x].sum=p[x*].sum+p[x*+].sum;
p[x].max1=max(p[x*].max1,p[x*+].max1);
if (p[x*].max1==p[x*+].max1)
{
p[x].num=p[x*].num+p[x*+].num;
p[x].max2=max(p[x*].max2,p[x*+].max2);
} else
{
re xx=p[x*],yy=p[x*+];
if (xx.max1<yy.max1) swap(xx,yy);
p[x].num=xx.num;
p[x].max2=max(xx.max2,yy.max1);
}
}
#define mid (h+t)/2
void build(int x,int h,int t)
{
p[x].h=h; p[x].t=t; p[x].lazy=INF;
if (h==t)
{
p[x].max1=b[h],p[x].max2=-INF,p[x].num=;
p[x].sum=b[h];
return;
}
build(x*,h,mid); build(x*+,mid+,t);
updata(x);
}
void down(int x)
{
if (p[x].max1<=p[x].lazy) p[x].lazy=INF;
if (p[x].lazy==INF) return;
if (p[x].h!=p[x].t)
{
if (p[x].lazy<p[x*].lazy) p[x*].lazy=p[x].lazy;
if (p[x].lazy<p[x*+].lazy) p[x*+].lazy=p[x].lazy;
}
if (p[x].max1>p[x].lazy&&p[x].max2<p[x].lazy)
{
p[x].sum=p[x].sum-1ll*(p[x].max1-p[x].lazy)*p[x].num;
p[x].max1=p[x].lazy;
} else
{
down(x*); down(x*+);
updata(x);
}
p[x].lazy=INF;
}
void change(int x,int h,int t,int w)
{
down(x);
if (p[x].h>t||p[x].t<h) return;
if (h<=p[x].h&&p[x].t<=t)
{
p[x].lazy=min(p[x].lazy,w); down(x); return;
}
change(x*,h,t,w); change(x*+,h,t,w);
updata(x);
}
int query1(int x,int h,int t)
{
down(x);
if (p[x].h>t||p[x].t<h) return(-INF);
if (h<=p[x].h&&p[x].t<=t) return(p[x].max1);
return(max(query1(x*,h,t),query1(x*+,h,t)));
}
ll query2(int x,int h,int t)
{
down(x);
if (p[x].h>t||p[x].t<h) return();
if (h<=p[x].h&&p[x].t<=t) return(p[x].sum);
return(query2(x*,h,t)+query2(x*+,h,t));
}
int main()
{
freopen("noip.in","r",stdin);
freopen("noip.out","w",stdout);
std::ios::sync_with_stdio(false);
cin>>T;
for (int ttt=;ttt<=T;ttt++)
{
// clear();
cin>>n>>m;
for (int i=;i<=n;i++) cin>>b[i];
build(,,n);
for (int i=;i<=m;i++)
{
int x,y,z,w;
cin>>x;
if (x==)
{
cin>>y>>z>>w;
change(,y,z,w);
}
if (x==)
{
cin>>y>>z;
cout<<query1(,y,z)<<endl;
}
if (x==)
{
cin>>y>>z;
cout<<query2(,y,z)<<endl;
}
}
}
return ;
}