专栏文章

题解：P11585 [KTSC 2022 R1] 直方图

云云浅知处はなび
P11585题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipnxnvy
此快照首次捕获于
2025/12/03 15:05
3 个月前
此快照最后确认于
2025/12/03 15:05
3 个月前
查看原文

f(1)f(1)

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

f(2)f(2)

如果两个矩形横坐标区间不交，只需要枚举分界点 ii，计算在直线 x=ix=i 前后的最大矩形面积，相加即可。
对于相交的情况，两个一定在笛卡尔树上成祖孙关系，考虑如果选了 u,vu,v 这两个点，其中 uu 是 vv 的祖先，其贡献为 −lenv×hu+lenu×hu+lenv×hv-len_v\times h_u+len_u\times h_u+len_v\times h_v。
在祖先处统计，李超树合并维护 (−len,len×h)(-len,len\times h) 的这些直线即可。

f(3)f(3)

对于三个矩形的横坐标区间互不相交的情况，DP 即可。
如果前两个矩形的横坐标区间都和第三个不交，类似 k=2k=2 的两个不交的部分做一遍即可。
设选的三个矩形对应到笛卡尔树上的节点分别为 u,v,wu,v,w。
如果 u,v,wu,v,w 依次为祖孙关系就只需要把 k=2k=2 的再做一遍。
具体来说我们设 GvG_v 表示选一个 vv 和 vv 的子孙 ww，其 −lenw×hv+lenv×hv+lenw×hw-len_w\times h_v+len_v\times h_v+len_w\times h_w 的最大值，再设 HuH_u 表示选一个 uu 和 uu 的子孙 vv，其 −lenv×hu+lenu×hu+Gv-len_v\times h_u+len_u\times h_u+G_v 的最大值，两个都可以用李超树优化。
剩下的唯一情况是选一个祖先 uu，然后选两个 v,wv,w 满足 v,wv,w 互不为祖孙关系，造成的贡献为
lenv×hv+lenw×hw+lenu×hu−(lenv+lenw)×hulen_v\times h_v+len_w\times h_w+len_u\times h_u-(len_v+len_w)\times h_u
我们考虑放宽限制，发现当 uu 不为 v,wv,w 的祖先时，这个东西不会算的更大。考虑对 uu 不做任何限制，只钦定 v,wv,w 不交。那么如果没有不交的限制，我们需要对一个 (−leni,leni×hi)(-len_i,len_i\times h_i) 这样的东西求一下凸包，然后和自己做闵可夫斯基和。
考虑如何处理不交的限制。对序列建线段树，每个子树变成一个区间 [l,r][l,r]，考虑两个不交区间 [l1,r1],[l2,r2][l_1,r_1],[l_2,r_2]，不妨设 r1<l2r_1<l_2，我们在 LCA(r1,l2)\text{LCA}(r_1,l_2) 处统计这个贡献。
具体来说，我们对每个线段树节点维护两个凸包 L,RL,R，然后对每个区间 [l,r][l,r]，我们在 ll 的所有祖先的 LL 凸包里面插入这个点，rr 的所有祖先的 RR 凸包里面插入这个点，然后我们对每个线段树节点，把他左儿子的 RR 凸包和右儿子的 LL 凸包做闵可夫斯基和，把得到的这些点放到总的点集里面，最后再对总的点集求一遍凸包。求出这个凸包之后，再枚举 uu 计算即可。
实现的时候写成分治的形式可以减小一部分常数。综上，总复杂度 O(nlog⁡n)O(n\log n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...