时间限制40.00s

猎奇暴力维护？

分块

每个块暴力储存当前值和历史最大值，写懒标记的方式，查询就是 push down 按照当前值排序一下，找到对应区间，做一次前缀 $max$。

push_down 比较神秘就是。

时间复杂度 $O(n\sqrt{n} \log{n})$

#include<bits/stdc++.h>
#define int long long
#define reg register
#define rep(i,a,b) for(reg int i=a;i<=b;++i)
#define drep(i,a,b) for(reg int i=a;i>=b;--i)
#define pb push_back
#define ins insert
using namespace std;
const int N=5e5+10,mod=2e18,B=477;
int a[N],b[N],L[N],R[N],rev[N],cnt;
struct Node{int op,l,r,x,ans;Node(){op=l=r=x=0,ans=-mod;}}o[N];
int l,r,ad,mxad;
struct st{int key,val;bool operator<(const st X)const{return key<X.key;}}c[N];
int pre[N],tmp[N];
void pushdown(){
	rep(i,l,r)b[i]=max(b[i],a[i]+mxad),a[i]+=ad;
	ad=mxad=0;
	rep(i,l,r)c[i]=st{a[i],b[i]};
	sort(c+l,c+r+1);
	pre[l-1]=-mod;
	rep(i,l,r)pre[i]=max(pre[i-1],c[i].val),tmp[i]=c[i].key;
}
void chmax(int &x,int y){
	if(x<y)x=y;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	rep(i,1,n)cin>>a[i],b[i]=a[i];
	rep(i,1,n){
		cnt=rev[i]=(i-1)/B+1;
		R[rev[i]]=i;if(!L[rev[i]])L[rev[i]]=i;
	}
	rep(i,1,m)cin>>o[i].op>>o[i].l>>o[i].r>>o[i].x;
	rep(p,1,rev[n]){ // range all block instead of time
		l=L[p],r=R[p],ad=mxad=0;
		pushdown();
		rep(i,1,m){
			if(r<o[i].l||o[i].r<l)continue;
			if(o[i].l<=l&&r<=o[i].r){
				if(o[i].op==1){ //add
					ad+=o[i].x,mxad=max(mxad,ad);
				}else{ //qry
					int pos=lower_bound(tmp+l,tmp+r+1,o[i].x-ad)-tmp-1;//get range max
					if(pos==l-1)continue;
					if(pos>=l)chmax(o[i].ans,max(pre[pos],tmp[pos]+mxad));
				}
			}else{
				if(o[i].op==1){ //add
					pushdown();
					rep(k,max(l,o[i].l),min(r,o[i].r))a[k]+=o[i].x;
					pushdown();
				}else{ //qry
					rep(k,max(l,o[i].l),min(r,o[i].r))if(a[k]+ad<o[i].x)
						chmax(o[i].ans,max(a[k]+mxad,b[k]));
				}
			}
		}
	}
	rep(i,1,m)if(o[i].op==2)cout<<(o[i].ans==-mod?"-inf":to_string(o[i].ans))<<"\n "[i==m];
	return 0;
}