题解：
线段树维护区间取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*4];
ll b[N];
int T,n,m;
il void updata(int x)
{
p[x].sum=p[x*2].sum+p[x*2+1].sum;
p[x].max1=max(p[x*2].max1,p[x*2+1].max1);
if (p[x*2].max1==p[x*2+1].max1)
{
p[x].num=p[x*2].num+p[x*2+1].num;
p[x].max2=max(p[x*2].max2,p[x*2+1].max2);
} else
{
re xx=p[x*2],yy=p[x*2+1];
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=1;
p[x].sum=b[h];
return;
}
build(x*2,h,mid); build(x*2+1,mid+1,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*2].lazy) p[x*2].lazy=p[x].lazy;
if (p[x].lazy<p[x*2+1].lazy) p[x*2+1].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*2); down(x*2+1);
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*2,h,t,w); change(x*2+1,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*2,h,t),query1(x*2+1,h,t)));
}
ll query2(int x,int h,int t)
{
down(x);
if (p[x].h>t||p[x].t<h) return(0);
if (h<=p[x].h&&p[x].t<=t) return(p[x].sum);
return(query2(x*2,h,t)+query2(x*2+1,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=1;ttt<=T;ttt++)
{
// clear();
cin>>n>>m;
for (int i=1;i<=n;i++) cin>>b[i];
build(1,1,n);
for (int i=1;i<=m;i++)
{
int x,y,z,w;
cin>>x;
if (x==0)
{
cin>>y>>z>>w;
change(1,y,z,w);
}
if (x==1)
{
cin>>y>>z;
cout<<query1(1,y,z)<<endl;
}
if (x==2)
{
cin>>y>>z;
cout<<query2(1,y,z)<<endl;
}
}
}
return 0;
}