专栏文章

题解：P14311 【MX-S8-T4】平衡三元组

qqczrz6v4nhp6u
P14311题解参与者 2已保存评论 1

文章操作

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

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

Solution

不妨思考一下若给定一个 BB，如何快速求出 f(B)f(B)。
  • Observation 1：最优解中 BxB_x 一定是序列的前缀最大值。
    证明：若存在 i<xi<x 使得 Bi>BxB_i> B_x，则将 x←ix\gets i 一定不劣。
  • Observation 2：最优解中 BzB_z 一定是序列的后缀最大值。
    证明：同上。
  • Observation 3：BxB_x 和 BzB_z 必有一个取到全局最大值。
    证明：固定 yy，若 ByB_y 为全局最大值显然成立；否则 BxB_x 和 BzB_z 会分别取到 B[1,y)B_{[1,y)} 和 B(y,∣B∣]B_{(y,|B|]} 的最大值，其中必有全局最大值。
接下来不妨认为 zz 取到了全局最大值，xx 取到的情况是类似的。将前缀最大值的位置抠出来，设其依次为 p1,p2,⋯ ,pmp_1,p_2,\cdots,p_m。
  • Observation 4：若 ByB_y 是前缀最大值且 y=pky=p_k，则 x=pk−1x=p_{k-1}。
    证明：显然。
  • Observation 5：若 ByB_y 是前缀最大值，则有贡献的 yy 只有 O(log⁡V)O(\log V) 个。
证明：设 y=pky=p_k，x=pk−1x=p_{k-1}。若 (x,y,z)(x,y,z) 不合法，则有 Bpk−Bpk−1>Bpm−BpkB_{p_k}-B_{p_{k-1}}>B_{p_m}-B_{p_k}，那么有 Bpm−Bpk−1>2(Bpm−Bpk)B_{p_m}-B_{p_{k-1}}>2(B_{p_m}-B_{p_k})。由于 0≤Bpm−Bpi≤Bpm0\le B_{p_m}-B_{p_i}\le B_{p_m}，至多 O(log⁡V)O(\log V) 轮后会找到第一个合法的 pkp_k，而往下继续找由于答案更小，是没有意义的。
  • Observation 6：若 ByB_y 不是前缀最大值，则我们无需检查 (x,y,z)(x,y,z) 的合法性（即此时一定有 By−Bx≤Bz−ByB_y-B_x\le B_z-B_y）。
    证明：显然此时一定有 Bx≥ByB_x\ge B_y 与 Bz≥ByB_z\ge B_y，不难发现一定合法。
在 ByB_y 是前缀最大值的部分迭代 O(log⁡V)O(\log V) 轮时顺便统计这部分的贡献即可，找到一个合法的是前缀最大值的 ByB_y 后继续往下找仍然是没有意义的。
那么线段树维护区间加、求区间 max⁡\max 及其位置即可做到 O(n+qlog⁡nlog⁡V)O(n+q\log n\log V)，可以通过。

Code

CPP
bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=1e6+5,mod=998244353,INF=1e9;
constexpr ll LINF=1e18;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)res=res*a%mod;
	return res;
}
int n,q,a[N];
struct node{
	int val,pos;
	node(){val=pos=0;}
	node(int _val,int _pos){val=_val,pos=_pos;}
};
inline bool operator <(const node &a,const node &b){
	return a.val<b.val;
}
int L[N<<2],R[N<<2],M[N<<2],Tag[N<<2];node Max[N<<2];
inline void pushup(int p){Max[p]=max(Max[p<<1],Max[p<<1|1]);}
inline void pushTag(int p,int v){Max[p].val+=v,Tag[p]+=v;}
inline void pushdown(int p){if(Tag[p])pushTag(p<<1,Tag[p]),pushTag(p<<1|1,Tag[p]),Tag[p]=0;}
void build(int l,int r,int p=1){
	L[p]=l,R[p]=r,M[p]=(l+r)>>1,Tag[p]=0;
	if(l==r){
		Max[p]=node(a[l],l);
		return;
	}
	build(L[p],M[p],p<<1);
	build(M[p]+1,R[p],p<<1|1);
	pushup(p);
}
inline void mdf(int l,int r,int v,int p=1){
	if(l<=L[p]&&R[p]<=r){
		pushTag(p,v);
		return;
	}
	pushdown(p);
	if(l<=M[p])mdf(l,r,v,p<<1);
	if(M[p]<r)mdf(l,r,v,p<<1|1);
	pushup(p);
}
inline node qry(int l,int r,int p=1){
	if(l<=L[p]&&R[p]<=r)return Max[p];
	pushdown(p);
	if(r<=M[p])return qry(l,r,p<<1);
	if(M[p]<l)return qry(l,r,p<<1|1);
	return max(qry(l,r,p<<1),qry(l,r,p<<1|1));
}
bool Med;
int main(){
	cerr<<abs(&Mst-&Med)/1048576.0<<endl;
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,n);
	while(q--){
		int op;cin>>op;
		if(op==1){
			int l,r;cin>>l>>r;
			ll ans=-LINF;node all=qry(l,r);
			int val=all.val,pos=all.pos;
			if(l<pos){
				node cur=qry(l,pos-1),nxt;
				for(int maxy=cur.pos+1<pos?qry(cur.pos+1,pos-1).val:-INF;cur.pos>=l;cur=nxt){
					int cval=cur.val,cpos=cur.pos;
					if(maxy>-INF)
						ans=max(ans,(ll)cval+maxy+val);
					if(l<cpos){
						nxt=qry(l,cpos-1);
						int nval=nxt.val,npos=nxt.pos;
						if(cval<=((nval+val)>>1)){
							ans=max(ans,(ll)nval+cval+val);
							break;
						}
						else if(npos+1<cpos)
							maxy=max(maxy,qry(npos+1,cpos-1).val);
					}
					else break;
				}
			}
			if(pos<r){
				node cur=qry(pos+1,r),nxt;
				for(int maxy=pos<cur.pos-1?qry(pos+1,cur.pos-1).val:-INF;cur.pos<=r;cur=nxt){
					int cval=cur.val,cpos=cur.pos;
					if(maxy>-INF)
						ans=max(ans,(ll)val+maxy+cval);
					if(cpos<r){
						nxt=qry(cpos+1,r);
						int nval=nxt.val,npos=nxt.pos;
						if(cval<=((val+nval)>>1)){
							ans=max(ans,(ll)val+cval+nval);
							break;
						}
						else if(cpos+1<npos)
							maxy=max(maxy,qry(cpos+1,npos-1).val);
					}
					else break;
				}
			}
			if(ans>-LINF)cout<<ans<<'\n';
			else cout<<"No\n";
		}
		else{
			int l,r,x;cin>>l>>r>>x;
			mdf(l,r,x);
		}
	}
	return 0;
}

评论

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

正在加载评论...