题目link

rt。四发全部T掉。

#include <iostream>
using namespace std;
const int MAXN=1e6+10;
long long tag[MAXN<<2],d[MAXN<<2],maxx[MAXN<<2],se[MAXN<<2],cnt[MAXN<<2],a[MAXN],n,m,x,y,v,opt;
void pushup(int p)
{
	int ls=p*2,rs=p*2+1; 
	d[p]=d[ls]+d[rs];
	if(maxx[ls]==maxx[rs])
	{
		maxx[p]=maxx[ls];
		se[p]=max(se[ls],se[rs]);
		cnt[p]=cnt[ls]+cnt[rs];
	}
	else if(maxx[ls]>maxx[rs])
	{
		maxx[p]=maxx[ls];
		se[p]=max(se[ls],maxx[rs]);
		cnt[p]=cnt[ls];
	}
	else
	{
		maxx[p]=maxx[rs];
		se[p]=max(maxx[ls],se[rs]);
		cnt[p]=cnt[rs];
	}
}
void tagged(int p,long long t)
{
	if(maxx[p]<=t) return;
	d[p]+=(t-maxx[p])*cnt[p];
	maxx[p]=tag[p]=t;
}
void pushdown(int p)
{
	if(tag[p]==-1) return;
	tagged(p*2,tag[p]);
	tagged(p*2+1,tag[p]);
	tag[p]=-1;
}
void build(int s,int t,int p)
{
	tag[p]=-1;
	if(s==t)
	{
		d[p]=a[s];
		se[p]=-1;
		maxx[p]=a[s];
		cnt[p]=1;
		return;
	}
	int m=(s+t)>>1;
	build(s,m,p*2);
	build(m+1,t,p*2+1);
	pushup(p);
}
void ar_min(int l,int r,int s,int t,int p,int v)
{
	if(maxx[p]<=v) return;
	if(l<=s&&t<=r&&se[p]<v)
	{
		tagged(p,v);
		return;
	}
	pushdown(p);
	int m=(s+t)>>1;
	if(l<=m) ar_min(l,r,s,m,p*2,v);
	if(r>m) ar_min(l,r,m+1,t,p*2+1,v);
	pushup(p);
}
int query_max(int l,int r,int s,int t,int p)
{
	if(l<=s&&t<=r) return maxx[p];
	int m=(s+t)>>1,ans=-1;
	if(l<=m) ans=max(ans,query_max(l,r,s,m,p*2));
	if(r>m) ans=max(ans,query_max(l,r,m+1,t,p*2+1));
	return ans;
} 
long long query_sum(int l,int r,int s,int t,int p)
{
	if(l<=s&&t<=r) return d[p];
	long long m=(s+t)>>1,ans=-1;
	if(l<=m) ans+=max(ans,query_sum(l,r,s,m,p*2));
	if(r>m) ans+=max(ans,query_sum(l,r,m+1,t,p*2+1));
	return ans;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++) cin>>a[i];
		build(1,n,1);
		while(m--)
		{
			cin>>opt>>x>>y;
			if(!opt)
			{
				cin>>v;
				ar_min(x,y,1,n,1,v);
			}
			else if(opt==1)
			{
				cout<<query_max(x,y,1,n,1)<<endl;
			}
			else
			{
				cout<<query_sum(x,y,1,n,1)<<endl;
			}
		}
	}
	return 0;
}