思路：
后面nlogn的部分是伪证...
吉老司机翻车了
//By SiriusRen #include <cstdio> #include <algorithm> using namespace std; const int N=1000050; int cases,n,m,op,xx,yy,zz; typedef long long ll; struct SegTree{int max1,max2,maxnum,lazy;ll sum;}tr[N*8]; void push_up(int pos){ tr[pos].max2=0;int lson=pos<<1,rson=pos<<1|1; tr[pos].max1=max(tr[lson].max1,tr[rson].max1); if(tr[lson].max1==tr[rson].max1) tr[pos].maxnum=tr[lson].maxnum+tr[rson].maxnum, tr[pos].max1=tr[lson].max1, tr[pos].max2=max(tr[lson].max2,tr[rson].max2); else{ tr[lson].max1>tr[rson].max1?tr[pos]=tr[lson]:tr[pos]=tr[rson]; tr[pos].max2=max(tr[lson].max2,tr[rson].max2); if(tr[pos].max1==tr[lson].max1)tr[pos].max2=max(tr[pos].max2,tr[rson].max1); else tr[pos].max2=max(tr[pos].max2,tr[lson].max1); }tr[pos].sum=tr[lson].sum+tr[rson].sum; } void change(int pos,int wei){ tr[pos].sum-=(1ll*tr[pos].max1-wei)*tr[pos].maxnum; tr[pos].max1=tr[pos].lazy=wei; } void push_down(int pos){ int lson=pos<<1,rson=pos<<1|1; if(tr[lson].max1>tr[pos].lazy)change(lson,tr[pos].lazy),tr[lson].lazy=tr[pos].lazy; if(tr[rson].max1>tr[pos].lazy)change(rson,tr[pos].lazy),tr[rson].lazy=tr[pos].lazy; tr[pos].lazy=-1; } void build(int l,int r,int pos){ tr[pos].lazy=-1,tr[pos].max2=0; if(l==r){scanf("%d",&tr[pos].max1),tr[pos].sum=tr[pos].max1,tr[pos].maxnum=1;return;} int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; build(l,mid,lson),build(mid+1,r,rson),push_up(pos); } void insert(int l,int r,int pos,int L,int R,int wei){ if(~tr[pos].lazy)push_down(pos); int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(l>=L&&r<=R){ if(wei>=tr[pos].max1)return; else if(wei<tr[pos].max1&&wei>tr[pos].max2){change(pos,wei);return;} else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei); } if(mid<L)insert(mid+1,r,rson,L,R,wei); else if(mid>=R)insert(l,mid,lson,L,R,wei); else insert(l,mid,lson,L,R,wei),insert(mid+1,r,rson,L,R,wei); push_up(pos); } ll query_sum(int l,int r,int pos,int L,int R){ if(~tr[pos].lazy)push_down(pos); if(l>=L&&r<=R)return tr[pos].sum; int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)return query_sum(mid+1,r,rson,L,R); else if(mid>=R)return query_sum(l,mid,lson,L,R); else return query_sum(l,mid,lson,L,R)+query_sum(mid+1,r,rson,L,R); } int query_max(int l,int r,int pos,int L,int R){ if(~tr[pos].lazy)push_down(pos); if(l>=L&&r<=R)return tr[pos].max1; int mid=(l+r)>>1,lson=pos<<1,rson=pos<<1|1; if(mid<L)return query_max(mid+1,r,rson,L,R); else if(mid>=R)return query_max(l,mid,lson,L,R); else return max(query_max(l,mid,lson,L,R),query_max(mid+1,r,rson,L,R)); } int read(){ char p=getchar();int x=0; while(p<'0'||p>'9')p=getchar(); while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar(); return x; } signed main(){ scanf("%d",&cases); while(cases--){ n=read(),m=read(),build(1,n,1); for(int i=1;i<=m;i++){ op=read(),xx=read(),yy=read(); if(!op)zz=read(),insert(1,n,1,xx,yy,zz); else if(op==1)printf("%d ",query_max(1,n,1,xx,yy)); else printf("%lld ",query_sum(1,n,1,xx,yy)); } } }