15011418730 LV 7 @ 2025-8-24 23:08:36

自动搬运

来自洛谷，原作者为

	云浅知处喵

搬运于2025-08-24 23:08:36，当前版本为作者最后更新于2025-04-10 15:24:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$f(1)$

建笛卡尔树，那么答案一定是选笛卡尔树上的一个矩形。容易做到 $O(n)$ 。

$f(2)$

如果两个矩形横坐标区间不交，只需要枚举分界点 $i$ ，计算在直线 $x=i$ 前后的最大矩形面积，相加即可。

对于相交的情况，两个一定在笛卡尔树上成祖孙关系，考虑如果选了 $u,v$ 这两个点，其中 $u$ 是 $v$ 的祖先，其贡献为 $-len_v\times h_u+len_u\times h_u+len_v\times h_v$ 。

在祖先处统计，李超树合并维护 $(-len,len\times h)$ 的这些直线即可。

$f(3)$

对于三个矩形的横坐标区间互不相交的情况，DP 即可。

如果前两个矩形的横坐标区间都和第三个不交，类似 $k=2$ 的两个不交的部分做一遍即可。

设选的三个矩形对应到笛卡尔树上的节点分别为 $u,v,w$ 。

如果 $u,v,w$ 依次为祖孙关系就只需要把 $k=2$ 的再做一遍。

具体来说我们设 $G_v$ 表示选一个 $v$ 和 $v$ 的子孙 $w$ ，其 $-len_w\times h_v+len_v\times h_v+len_w\times h_w$ 的最大值，再设 $H_u$ 表示选一个 $u$ 和 $u$ 的子孙 $v$ ，其 $-len_v\times h_u+len_u\times h_u+G_v$ 的最大值，两个都可以用李超树优化。

剩下的唯一情况是选一个祖先 $u$ ，然后选两个 $v,w$ 满足 $v,w$ 互不为祖孙关系，造成的贡献为

$$len_v\times h_v+len_w\times h_w+len_u\times h_u-(len_v+len_w)\times h_u $$

我们考虑放宽限制，发现当 $u$ 不为 $v,w$ 的祖先时，这个东西不会算的更大。考虑对 $u$ 不做任何限制，只钦定 $v,w$ 不交。那么如果没有不交的限制，我们需要对一个 $(-len_i,len_i\times h_i)$ 这样的东西求一下凸包，然后和自己做闵可夫斯基和。

考虑如何处理不交的限制。对序列建线段树，每个子树变成一个区间 $[l,r]$ ，考虑两个不交区间 $[l_1,r_1],[l_2,r_2]$ ，不妨设 $r_1<l_2$ ，我们在 $\text{LCA}(r_1,l_2)$ 处统计这个贡献。

具体来说，我们对每个线段树节点维护两个凸包 $L,R$ ，然后对每个区间 $[l,r]$ ，我们在 $l$ 的所有祖先的 $L$ 凸包里面插入这个点， $r$ 的所有祖先的 $R$ 凸包里面插入这个点，然后我们对每个线段树节点，把他左儿子的 $R$ 凸包和右儿子的 $L$ 凸包做闵可夫斯基和，把得到的这些点放到总的点集里面，最后再对总的点集求一遍凸包。求出这个凸包之后，再枚举 $u$ 计算即可。

实现的时候写成分治的形式可以减小一部分常数。综上，总复杂度 $O(n\log n)$ 。

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=5e5+5;
int n,a[N],pl[N],pr[N],fa[N],len[N],H;
ll pre[N],suf[N];
int rt=0;
vector<int>G[N];

ll ans1,ans2,ans3;

void build(){
	vector<int>stk(n+1);int top=0;
	for(int i=1;i<=n;i++){
		while(top>0&&a[stk[top]]>a[i])top--;
		pl[i]=stk[top]+1,stk[++top]=i;
	}
	top=0,stk[0]=n+1;
	for(int i=n;i>=1;i--){
		while(top>0&&a[stk[top]]>=a[i])top--;
		pr[i]=stk[top]-1,stk[++top]=i;
	}

	for(int i=1;i<=n;i++){
		len[i]=pr[i]-pl[i]+1;
		if(pl[i]==1&&pr[i]==n)rt=i;
		else if(pl[i]==1)fa[i]=pr[i]+1;
		else if(pr[i]==n)fa[i]=pl[i]-1;
		else fa[i]=(a[pl[i]-1]>a[pr[i]+1]?pl[i]-1:pr[i]+1);

		if(i!=rt)G[fa[i]].emplace_back(i);
	}

	for(int i=1;i<=n;i++){
		ll cur=1ll*(pr[i]-pl[i]+1)*a[i];
		cmax(suf[pl[i]],cur),cmax(pre[pr[i]],cur),cmax(ans1,cur);
	}
	for(int i=1;i<=n;i++)cmax(pre[i],pre[i-1]);
	for(int i=n;i>=1;i--)cmax(suf[i],suf[i+1]);
}

struct LINE{
	ll k,b;
	ll val(int x){return k*x+b;}
	LINE(ll K=0,ll B=0):k(K),b(B){}
};
bool cmp(LINE A,LINE B,int pos){
	return A.val(pos)>B.val(pos);
}

const ll INF=1e12;

int root[N];
const int M=N*32;
struct LiChao{
	LINE d[M];int tot,ls[M],rs[M];
	#define ls(p) (ls[p])
	#define rs(p) (rs[p])
	void reset(){
		memset(ls,0,sizeof(ls)),memset(rs,0,sizeof(rs)),tot=0;
		for(int i=0;i<M;i++)d[i]=LINE(-INF,-INF);
	}
	void clear(){
		for(int i=1;i<=tot;i++)d[i]=LINE(-INF,-INF),ls[i]=rs[i]=0;
		tot=0;
	}
	void upd(int ql,int qr,int &p,LINE A){
		if(!p)return d[p=++tot]=A,void();
		int mid=(ql+qr)>>1;
		if(cmp(A,d[p],mid))swap(d[p],A);
		if(cmp(A,d[p],ql))upd(ql,mid,ls(p),A);
		if(cmp(A,d[p],qr))upd(mid+1,qr,rs(p),A);
	}
	ll qval(int x,int ql,int qr,int p){
		if(!p)return -INF;
		int mid=(ql+qr)>>1;ll ans=d[p].val(x);
		if(x<=mid)cmax(ans,qval(x,ql,mid,ls(p)));
		if(x>mid)cmax(ans,qval(x,mid+1,qr,rs(p)));
		return ans;
	}
	int merge(int p,int q,int l,int r){
		if(!p||!q)return p^q;
		upd(l,r,p,d[q]);int mid=(l+r)>>1;
		if(l!=r)ls[p]=merge(ls[p],ls[q],l,mid),rs[p]=merge(rs[p],rs[q],mid+1,r);
		return p;
	}
	#undef ls
	#undef rs
}T;

ll val[N];
void solve2(){
	function<void(int)>dfs=[&](int u){
		for(int v:G[u])dfs(v),root[u]=T.merge(root[u],root[v],1,H);
		T.upd(1,H,root[u],LINE(-len[u],1ll*len[u]*a[u]));
		val[u]=T.qval(a[u],1,H,root[u])+1ll*len[u]*a[u];
	};

	T.reset(),dfs(rt);
	for(int i=1;i<=n+1;i++)cmax(ans2,pre[i-1]+suf[i]);
	for(int i=1;i<=n;i++)cmax(ans2,val[i]);
}

struct P{ll x,y;P(ll _x=0,ll _y=0):x(_x),y(_y){}};
P operator-(P A,P B){return P(A.x-B.x,A.y-B.y);}
P operator+(P A,P B){return P(A.x+B.x,A.y+B.y);}
bool operator<(P A,P B){
	if(A.x!=B.x)return A.x<B.x;
	return A.y<B.y;
}
ll Cross(P A,P B){return A.x*B.y-A.y*B.x;}
bool chk(int k,P A,P B){// slope(A,B) > k ?
	return (B.y-A.y)>1ll*(B.x-A.x)*k;
}
struct kevin{
	vector<P>stk;int p=0;
	void clr(){stk.clear();p=0;}
	void ins(P A){
		while(stk.size()>=2&&Cross(stk.back()-A,stk[stk.size()-2]-A)<=0)stk.pop_back();
		stk.emplace_back(A);
	}
	ll qry(int k){
		if(stk.empty())return -INF;
		while(p+1<stk.size()&&chk(k,stk[p],stk[p+1]))p++;
		return -1ll*stk[p].x*k+stk[p].y;
	}
};

kevin All;
ll all_ps[N<<2];
void work(vector<P>A,vector<P>B){
	if(A.empty()||B.empty())return ;
	
	vector<P>C;
	for(int i=A.size()-1;i>=1;i--)A[i]=A[i]-A[i-1];
	for(int i=B.size()-1;i>=1;i--)B[i]=B[i]-B[i-1];
	int it=1;
	C.emplace_back(A[0]+B[0]);
	for(int i=1;i<A.size();i++){
		while(it<B.size()&&Cross(B[it],A[i])<0)C.emplace_back(B[it++]);
		C.emplace_back(A[i]);
	}
	while(it<B.size())C.emplace_back(B[it++]);
	for(int i=1;i<C.size();i++)C[i]=C[i]+C[i-1];

	for(auto W:C)cmax(all_ps[W.x],W.y);
}

vector<P>bl[N],br[N];
pair<vector<P>,vector<P> > Solve(int l,int r){
	if(l==r)return mk(bl[l],br[l]);
	int mid=(l+r)>>1;
	auto Lp=Solve(l,mid),Rp=Solve(mid+1,r);
	vector<P>curL,curR;
	auto wL=Lp.fi,wR=Rp.fi;
	int itp=0;
	for(int i=0;i<wL.size();i++){
		while(itp<wR.size()&&wR[itp]<wL[i])curL.emplace_back(wR[itp++]);
		curL.emplace_back(wL[i]);
	}
	while(itp<wR.size())curL.emplace_back(wR[itp++]);

	wL=Lp.se,wR=Rp.se,itp=0;
	for(int i=0;i<wL.size();i++){
		while(itp<wR.size()&&wR[itp]<wL[i])curR.emplace_back(wR[itp++]);
		curR.emplace_back(wL[i]);
	}
	while(itp<wR.size())curR.emplace_back(wR[itp++]);

	kevin L,R;L.clr(),R.clr();
	for(auto W:Lp.se)L.ins(W);
	for(auto W:Rp.fi)R.ins(W);
	work(L.stk,R.stk);

	return mk(curL,curR);
}

void solve3(){
	for(int i=1;i<=n;i++)cmax(ans3,val[i]+max(pre[pl[i]-1],suf[pr[i]+1]));

	vector<vector<ll> >dp(n+1,vector<ll>(4));
	vector<vector<pair<ll,int> > >Is(n+1);
	for(int i=1;i<=n;i++)Is[pr[i]].emplace_back(mk(1ll*len[i]*a[i],pl[i]-1));
	for(int i=1;i<=n;i++){
		for(int c=1;c<=3;c++){
			cmax(dp[i][c],dp[i-1][c]);
			for(auto [val,j]:Is[i])cmax(dp[i][c],dp[j][c-1]+val);
		}
		cmax(ans3,dp[i][3]);
	}

	function<void(int)>dfs=[&](int u){
		for(int v:G[u])dfs(v),root[u]=T.merge(root[u],root[v],1,H);
		cmax(ans3,T.qval(a[u],1,H,root[u])+1ll*len[u]*a[u]);
		T.upd(1,H,root[u],LINE(-len[u],val[u]));
	};
	for(int i=1;i<=n;i++)root[i]=0;
	T.reset(),dfs(rt);

	vector<int>ids(n);
	for(int i=0;i<n;i++)ids[i]=i+1;

	for(int i=1;i<=n;i++)br[pr[i]].emplace_back(P(len[i],1ll*len[i]*a[i])),bl[pl[i]].emplace_back(P(len[i],1ll*len[i]*a[i]));
	for(int i=1;i<=n;i++)sort(br[i].begin(),br[i].end()),sort(bl[i].begin(),bl[i].end());
	for(int i=1;i<=n;i++)all_ps[i]=-INF;
	Solve(1,n);
	for(int i=1;i<=n;i++)if(all_ps[i]>-INF){
		auto W=P(i,all_ps[i]);
		All.ins(W);
	}

	sort(ids.begin(),ids.end(),[&](int x,int y){return a[x]>a[y];});
	for(int i:ids)cmax(ans3,All.qry(a[i])+1ll*len[i]*a[i]);
}

vector<ll>max_area(vector<int>hh){
	n=hh.size();
	for(int i=1;i<=n;i++)a[i]=hh[i-1];
	for(int i=1;i<=n;i++)cmax(H,a[i]);

	build(),solve2(),solve3();

	vector<ll>ret;
	ret.emplace_back(ans1),ret.emplace_back(ans2),ret.emplace_back(ans3);
	return ret;
}

signed main(void){

	n=read();
	for(int i=1;i<=n;i++)a[i]=read(),cmax(H,a[i]);

	build(),solve2(),solve3();
	cout<<ans1<<" "<<ans2<<" "<<ans3<<endl;

	return 0;
}

ID

11356

时间

4000ms

内存

1024MiB

难度

标签

递交数

已通过

上传者

Hydro

1 条题解

自动搬运

以下是正文

$f(1)$

$f(2)$

$f(3)$

[KTSC 2022 R1] 直方图

信息

1 条题解

自动搬运

以下是正文

f(1)f(1)f(1)

f(2)f(2)f(2)

f(3)f(3)f(3)

[KTSC 2022 R1] 直方图

信息

还没有账户？

登录

$f(1)$

$f(2)$

$f(3)$