自动搬运

查看原文

来自洛谷，原作者为

	cyffff Not yet for the story on the last page, it's not the end.

搬运于2025-08-24 22:24:02，当前版本为作者最后更新于2023-02-09 13:14:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\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~