$\text{Link}$

在学习了“$\text{KTT}$” 之后（我的学习笔记）的一个暴力思路。我个人认为这个思路比讨论个数的思路更简洁，需要的讨论也更少。其它题解都被 hack 了才写的这篇。

这篇题解里没有明确说的内容都在学习笔记里有说。

题意

区间对 $x$ 取 $\max$，区间最大子段和。

$n\le 10^5$，$q\le 2\times10^5$。

思路

看到取 $\max$ 操作我们可以先放一个吉司机线段树，维护 $\min$ 和 $\text{secmin}$，修改时若 $x\le\min$ 直接返回；若 $\min<x<\text{secmin}$，对当前结点的所有最小值修改；若 $x\ge\text{secmin}$，则递归左右子树。

我们沿用 P5693 的思路，考虑用一次函数来表达 $sum,lmax,rmax,totmax$。

考虑 $ls+b$，我们考虑 $l$ 表示的是会变化的数的个数，在这里由于只修改最小值，则 $l$ 为选取的区间中最小值的个数。

考虑每个结点 $x$ 的含义，为最小值增加 $x$ 时就会发生变化。（如果最小值加 $x$ 大于次小值也无需特殊处理，吉司机线段树帮助我们处理了这样的情况）

在 pushup 中，我们需要将没有最小值的一边（即最小值不是整个区间的最小值的半个区间）的 $sum,lmax,rmax,totmax$ 的 $l$ 都设为 $0$ 再上传，原因就是我们在上面修改了 $l$ 的定义。

时间复杂度：不会算，有没有人可以分析一下？（或许和 P5693 复杂度一样，为 $O((n+m)\log^3n+q\log n)$，$m$ 为修改次数，$q$ 为询问次数）

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=1e5+10;
const ll INF=1e15;
int n,Q,p[N];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define pfl pair<Func,ll>
#define mpr make_pair
#define fi first
#define se second
struct Func{
	int k;
	ll b;
	inline friend Func operator+(const Func &a,const Func &b){
		return (Func){a.k+b.k,a.b+b.b};
	}
	inline void add(ll v){ b+=k*v; }
	inline void set(){ k=0; }
};
inline pfl max(Func a,Func b){
	if(a.k<b.k||a.k==b.k&&a.b<b.b) swap(a,b);
	if(a.b>=b.b) return mpr(a,INF);
	return mpr(b,(b.b-a.b)/(a.k-b.k));
}
struct node{
	Func lmax,rmax,totmax,sum;
	ll x;
	inline friend node operator+(const node &a,const node &b){
		node t;
		pfl tmp;
		t.x=min(a.x,b.x);
		tmp=max(a.lmax,b.lmax+a.sum);
		t.lmax=tmp.fi,t.x=min(t.x,tmp.se);
		tmp=max(b.rmax,a.rmax+b.sum);
		t.rmax=tmp.fi,t.x=min(t.x,tmp.se);
		tmp=max(a.totmax,b.totmax);
		t.x=min(t.x,tmp.se);
		tmp=max(tmp.fi,a.rmax+b.lmax);
		t.totmax=tmp.fi,t.x=min(t.x,tmp.se);
		t.sum=a.sum+b.sum;
		return t;
	}
	inline node set(){
		node a=*this;
		a.lmax.set(),a.rmax.set(),a.totmax.set(),a.sum.set();
		return a;
	}
};
struct KTT{
	node a[N<<2];
	ll tag[N<<2],mnn[N<<2],sec[N<<2];
	inline void pushup(int rt){
		if(mnn[ls]==mnn[rs]){
			mnn[rt]=mnn[ls];
			sec[rt]=min(sec[ls],sec[rs]); 
			a[rt]=a[ls]+a[rs];
		}
		if(mnn[ls]<mnn[rs]){
			mnn[rt]=mnn[ls];
			sec[rt]=min(sec[ls],mnn[rs]); 
			a[rt]=a[ls]+a[rs].set();
		}
		if(mnn[ls]>mnn[rs]){
			mnn[rt]=mnn[rs];
			sec[rt]=min(mnn[ls],sec[rs]); 
			a[rt]=a[ls].set()+a[rs];
		}
	}
	inline void build(int rt,int l,int r){
		tag[rt]=-INF;
		if(l==r){
			Func q={1,p[l]};
			a[rt]=(node){q,q,q,q,INF};
			mnn[rt]=p[l],sec[rt]=INF;
			return ;
		}
		int mid=(l+r)>>1;
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(rt);
	}
	inline void push(int rt,ll w){
		if(w<=mnn[rt]) return ;
		ll v=w-mnn[rt];
		mnn[rt]=w;
		tag[rt]=max(tag[rt],w);
		a[rt].x-=v;
		a[rt].lmax.add(v);
		a[rt].rmax.add(v);
		a[rt].sum.add(v);
		a[rt].totmax.add(v);
	}
	inline void defeat(int rt,int l,int r,ll v){
		tag[rt]=max(tag[rt],v);
		if(v-mnn[rt]>a[rt].x){
			int mid=l+r>>1;
			defeat(ls,l,mid,v);
			defeat(rs,mid+1,r,v);
			pushup(rt);
		}else{
			push(rt,v);
		}
	}
	inline void pushdown(int rt){
		if(tag[rt]!=-INF){
			ll bas=tag[rt];
			tag[rt]=-INF;
			push(ls,bas);
			push(rs,bas);
		}
	}
	inline void update(int rt,int l,int r,int L,int R,int k){
		if(mnn[rt]>=k) return ;
		if(L<=l&&r<=R&&k<sec[rt]){
			defeat(rt,l,r,k);
			return ;
		}
		pushdown(rt);
		int mid=l+r>>1;
		if(L<=mid) update(ls,l,mid,L,R,k);
		if(R>mid) update(rs,mid+1,r,L,R,k);
		pushup(rt);
	}
	inline node query(int rt,int l,int r,int L,int R){
		if(L<=l&&r<=R){
			return a[rt];
		}
		pushdown(rt);
		int mid=l+r>>1;
		if(R<=mid) return query(ls,l,mid,L,R);
		if(L>mid) return query(rs,mid+1,r,L,R);
		return query(ls,l,mid,L,mid)+query(rs,mid+1,r,mid+1,R);
	}
}t;
int main(){
	n=read(),Q=read();
	for(int i=1;i<=n;i++){
		p[i]=read();
	}
	t.build(1,1,n);
	while(Q--){
		int opt=read();
		switch(opt){
			case 0:{
				int l=read(),r=read(),v=read();
				t.update(1,1,n,l,r,v);
				break;
			}
			case 1:{
				int l=read(),r=read();
				write(max(0ll,t.query(1,1,n,l,r).totmax.b)),putc('\n');
				break;
			}
		}
	}
	flush();
    return 0;
} 

再见 qwq~

#include<bits/stdc++.h>
#define MAXN 100005
#define inf 1e18
#define ls k<<1
#define rs k<<1|1
#define mkp make_pair
using namespace std;

inline long long read(){
	long long x=0;
	int f=1;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}

int n,q;
long long A[MAXN];

struct line{
	long long k,b;
	line operator + (const line &a) const{
		return (line){k+a.k,b+a.b};
	}
	void add(long long v){
		b+=k*v;
	}
};

pair<line,long long> max(line a,line b){
	if(a.k<b.k || (a.k==b.k && a.b<b.b)) swap(a,b);
	if(a.b>=b.b) return mkp(a,inf);
	else return mkp(b,(b.b-a.b)/(a.k-b.k));
}

struct node{
	int l,r;
	line lmx,rmx,sum,totmx;
	long long x;//阈值
	long long mn,semn;
	long long tag;//tag维护要变成的值 不是变化量哦
	//我最开始写的是变化量（因为之前做过P6242） 然后发现又加又减有很多分类讨论不好写也不好调 所以重构了一遍代码改成要变成的值了 这样可以直接取max
	node convert(){
		node a=*this;
		a.lmx.k=a.rmx.k=a.sum.k=a.totmx.k=0;
		return a;
	}
}t[MAXN<<2];

void add(node &res,node a,node b){
	pair<line,long long> tmp;
	res.x=min(a.x,b.x);
	//sum=ls.sum+rs.sum
	res.sum=a.sum+b.sum;
	//lmax=max(ls.lmax,ls.sum+rs.lmax)
	tmp=max(a.lmx,a.sum+b.lmx);
	res.lmx=tmp.first;
	res.x=min(res.x,tmp.second);
	//rmax=max(rs.rmax,rs.sum+ls.rmax)
	tmp=max(b.rmx,b.sum+a.rmx);
	res.rmx=tmp.first;
	res.x=min(res.x,tmp.second);
	//totmax=max(ls.totmax,rs.totmax,ls.rmax+rs.lmax)
	tmp=max(a.totmx,b.totmx);
	res.x=min(res.x,tmp.second);
	tmp=max(tmp.first,a.rmx+b.lmx);
	res.totmx=tmp.first;
	res.x=min(res.x,tmp.second);
}
/*
这个地方如果你把吉司机要维护的值和KTT分开其实重载运算符很方便的
当然也可以令一个tmp把属于吉司机的信息记一下 更新完KTT之后再还原现场
总之就是如果把所有信息都封装在一起了 注意更新KTT的时候别把吉司机搞没了就行
*/

void pushup(int k){
	if(t[ls].mn==t[rs].mn){
		t[k].semn=min(t[ls].semn,t[rs].semn);
		t[k].mn=t[ls].mn;
		add(t[k],t[ls],t[rs]);
	}else if(t[ls].mn<t[rs].mn){
		t[k].semn=min(t[ls].semn,t[rs].mn);
		t[k].mn=t[ls].mn;
		add(t[k],t[ls],t[rs].convert());//打过吉司机的都知道吧 只有最值参与区间修改 所以肯定是最值在哪一个儿子上就要哪个的信息啊 这里的k可以感性理解一下吉司机的mncnt 为了方便暂时把另一个清空就行
	}else{
		t[k].semn=min(t[ls].mn,t[rs].semn);
		t[k].mn=t[rs].mn;
		add(t[k],t[ls].convert(),t[rs]);
	}
}

void build(int k,int l,int r){
	t[k].l=l;t[k].r=r;
	t[k].tag=-inf;//因为是维护的变成哪个值要取max所以是-inf 维护变化量的不用管
	if(l==r){
		line tmp={1,A[l]};
		t[k].lmx=t[k].rmx=t[k].sum=t[k].totmx=tmp;
		t[k].x=inf;
		t[k].mn=A[l];
		t[k].semn=inf;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(k);
}

void calc(node &res,long long v){
	if(t[res].mn>=v) return;
	long long tmp=v-t[res].mn;
	t[res].mn=v;
	t[res].tag=max(t[res].tag,v);
	t[res].sum.add(tmp);
	t[res].totmx.add(tmp);
	t[res].lmx.add(tmp);
	t[res].rmx.add(tmp);
	t[res].x-=tmp;
}

void pushdown(int k){
	if(t[k].tag!=-inf){
		calc(ls,t[k].tag);
		calc(rs,t[k].tag);
		t[k].tag=-inf;
	}
}

void upd(int k,long long v){
	t[k].tag=max(t[k].tag,v);
	long long tmp=v-t[k].mn;
	if(tmp>t[k].x){//超过阈值啦！ 直接重构
		upd(ls,v);
		upd(rs,v);
		pushup(k);
	}else{
		calc(k,v);
	}
}

void update(int k,int l,int r,long long v){
	if(t[k].mn>=v) return;
	if(t[k].l>=l && t[k].r<=r && t[k].semn>v){//之前打吉司机错过这里 注意是>不是>= 不然次小值就不严格啦！
		upd(k,v);
		return;
	}
	pushdown(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=l){
		update(ls,l,r,v);
	}
	if(mid<r){
		update(rs,l,r,v);
	}
	pushup(k);
}

node query(int k,int l,int r){
	if(t[k].l>=l && t[k].r<=r){
		return t[k];
	}
	pushdown(k);
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=r) return query(ls,l,r);
	if(mid<l) return query(rs,l,r);
	node res;
	res=res.convert();//像我这种写法要注意这里初始化要写好哦 不然会收获一份样例能过但WA0pts的代码
	add(res,query(ls,l,r),query(rs,l,r));
	return res;
}

int main(){
//	freopen("P6792.in","r",stdin);
//	freopen("P6792.out","w",stdout);
	n=read();q=read();
	for(int i=1;i<=n;i++){
		A[i]=read();
	}
	build(1,1,n);
	int op,l,r;
	long long x;
	while(q--){
		op=read();
		l=read();r=read();
		if(op==0){
			x=read();
			update(1,l,r,x);
		}else{
			long long ans=query(1,l,r).totmx.b;
			printf("%lld\n",max(0ll,ans));//注意题面上说可以取空集！ 所以一定要和0取一下max 我因为这个点WA75pts调了好久QwQ
		}
	}
	return 0;
}
//一点小建议：样例给的比较弱只有全局查询 调不出来的宝子可以自己造点有区间查询的数据 或者用小数据拍一拍什么的