如果维护max，sum，那么可以得到一个暴力方法，如果t>=max，那可以return，否则往下更新，显然超时。
在上面基础上，再维护一下次大值，与最大值的个数。这样一来，次大值<t<最大值 这样的情况也可以更新完了之后直接return，pushDown的话也很好操作。
实践证明，这样的复杂度降到了nlog(n)，具体证明可以看吉如一论文。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } template <class T> inline void read(T &x) { char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } } const int maxn=1000010; struct Seg { LL sum; int a,b,num; bool flag; }s[4*maxn]; int T,n,m; int M(int a,int b) { if(a>b) return a; return b; } int CI(int x,int a,int b,int c,int d) { if(a==b&&a==c&&a==d) return x; int res=0; if(a!=x) res=M(res,a); if(b!=x) res=M(res,b); if(c!=x) res=M(res,c); if(d!=x) res=M(res,d); return res; } void pushUp(int rt) { s[rt].sum=s[2*rt].sum+s[2*rt+1].sum; s[rt].a=M(s[2*rt].a,s[2*rt+1].a); s[rt].b=CI(s[rt].a,s[2*rt].a,s[2*rt].b,s[2*rt+1].a,s[2*rt+1].b); s[rt].num=0; if(s[2*rt].a==s[rt].a) s[rt].num=s[rt].num+s[2*rt].num; if(s[2*rt+1].a==s[rt].a) s[rt].num=s[rt].num+s[2*rt+1].num; } void pushDown(int rt) { if(s[rt].flag==0) return; int MAX=M(s[2*rt].a,s[2*rt+1].a); int t=s[rt].a; if(s[2*rt].a==MAX) { s[2*rt].flag=1; s[2*rt].sum=s[2*rt].sum-(LL)(s[2*rt].a-t)*s[2*rt].num; if(s[2*rt].a==s[2*rt].b) s[2*rt].a=s[2*rt].b=t; else s[2*rt].a=t; } if(s[2*rt+1].a==MAX) { s[2*rt+1].flag=1; s[2*rt+1].sum=s[2*rt+1].sum-(LL)(s[2*rt+1].a-t)*s[2*rt+1].num; if(s[2*rt+1].a==s[2*rt+1].b) s[2*rt+1].a=s[2*rt+1].b=t; else s[2*rt+1].a=t; } s[rt].flag=0; } void build(int l,int r,int rt) { s[rt].num=s[rt].a=s[rt].b=s[rt].sum=0; s[rt].flag=0; if(l==r) { scanf("%d",&s[rt].a); s[rt].b=s[rt].a; s[rt].sum=(LL)s[rt].b; s[rt].num=1; return; } int m=(l+r)/2; build(l,m,2*rt); build(m+1,r,2*rt+1); pushUp(rt); } int f(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return s[rt].a; int m=(l+r)/2; int x1=0,x2=0; pushDown(rt); if(L<=m) x1=f(L,R,l,m,2*rt); if(R>m) x2=f(L,R,m+1,r,2*rt+1); pushUp(rt); return max(x1,x2); } LL sum(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return s[rt].sum; int m=(l+r)/2; LL x1=0,x2=0; pushDown(rt); if(L<=m) x1=sum(L,R,l,m,2*rt); if(R>m) x2=sum(L,R,m+1,r,2*rt+1); pushUp(rt); return x1+x2; } void force(int t,int l,int r,int rt) { if(s[rt].a<=t) return; if(l==r) { s[rt].a=s[rt].b=s[rt].sum=t; return ; } if(s[rt].b<t) { s[rt].flag=1; s[rt].sum=s[rt].sum-(LL)(s[rt].a-t)*s[rt].num; s[rt].a=t; return; } if(s[rt].b==s[rt].a) { s[rt].flag=1; s[rt].sum=s[rt].sum-(LL)(s[rt].a-t)*s[rt].num; s[rt].b=s[rt].a=t; return; } pushDown(rt); int m=(l+r)/2,tag=0; if(s[2*rt].a>t) force(t,l,m,2*rt),tag=1; if(s[2*rt+1].a>t) force(t,m+1,r,2*rt+1),tag=1; if(tag==1) pushUp(rt); } void update(int L,int R,int t,int l,int r,int rt) { if(s[rt].a<=t) return; if(L<=l&&r<=R) { force(t,l,r,rt); return ; } pushDown(rt); int m=(l+r)/2,tag=0; if(L<=m&&s[2*rt].a>t) update(L,R,t,l,m,2*rt),tag=1; if(R>m&&s[2*rt+1].a>t) update(L,R,t,m+1,r,2*rt+1),tag=1; if(tag==1) pushUp(rt); } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); build(1,n,1); for(int i=1;i<=m;i++) { int op,x,y; scanf("%d%d%d",&op,&x,&y); if(op==0) { int t; read(t); update(x,y,t,1,n,1); } else if(op==1) printf("%d ",f(x,y,1,n,1)); else printf("%lld ",sum(x,y,1,n,1)); } } return 0; }