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

我们从暴力开始考虑，对于一个确定的区间

[l,r]

和

y

，

A_x

和

A_z

一定会取到

[l,y)

和

(y,r]

的前/后缀最大值。

感性理解一下，

y

确定时，

A_x

和

A_z

越大，更容易满足

2 \times A_y \le A_x + A_z

的限制，同时会使价值更大，是一个双赢的局面。

处理一下区间前/后缀最大值，枚举

y

，即可做到

O(nq)

的暴力做法。

进一步思考，当答案最优时，

A_x

或

A_z

一定会取到区间内的最大值(除非

y

不得不取到最大值)，所以我们就可以确定三元组的一个端点。

我们先考虑

A_x

取到最大值的情况，设

m_0=x

，我们求出

(pos,r]

的最大值的位置为

m_1

，那么所有在

(m_0,m_1)

之间的

y

都是合法的，因为限制式子相当于让

A_y \le \frac{A_x+A_z}{2}

，现在

A_{m_0}

和

A_{m_1}

都大于等于

A_y

，所以他们的平均值也一定大于等于

A_y

，所以我们直接取

(m_0,m_1)

中的

A

的最大值计算贡献即可。

接下来我们

y=m_1

的情况，

x,y

已经确定，

z

沿用暴力时的思路，取

(m_1,r]

中的最大值

m_2

作为

z

判断是否合法。

如果合法，该答案即为最优答案，因为

m_0,m_1,m_2

分别是可取区间内的最大值的位置，不会再有合法区间内的其他值使答案更优。

如果不合法，我们继续向后重复这个过程，选定

m_2

为

(m_1,r]

区间内的最大值的位置，对这个子问题递归求解即可，直到满足要求或区间长度不足选出两个数。

m_0=z

的情况同理。

最后我们证明时间复杂度：

主要的复杂度分析在于递归的次数的数量级，我们考虑何时会进行下一层递归:

2 \times A_{m_1} > A_{m_0}+A_{m_2}

移项得

A_{m_2} < 2 \times A_{m_1}-A_{m_0}

子问题的递归条件同理为

A_{m_3} < 2\times A_{m_2} -A_{m_0} =4 \times A_{m_1} -3\times A_{m_0}

归纳总结可得递归条件为

A_{m_n} <2^{n-1} (A_{m_1} - A_{m_0}) +A_{m_0}

显然最多递归

\log V

次，其中

V

为值域。

我们在这个过程中只用到了求区间最大值及其位置，可以用线段树平凡的维护，修改操作的区间加是平凡的。

所以复杂度为

O(q\log n \log V)

这道题的代码是比较好写的，是一道偏思维的 DS 题。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[(int)2e6];
struct Seg{
	#define ls i<<1
	#define rs i<<1|1
	#define mid ((l+r)>>1)
	int mx[(int)5e6],pos[(int)5e6],laz[(int)5e6];
	void build(int i,int l,int r){
		if(l==r)return mx[i]=a[l],pos[i]=l,void();
		build(ls,l,mid),build(rs,mid+1,r),push_up(i);
	}
	void down(int i){
		if(!laz[i])return ;
		mx[ls]+=laz[i],mx[rs]+=laz[i];
		laz[ls]+=laz[i],laz[rs]+=laz[i];laz[i]=0;
	}
	void push_up(int i){
		mx[i]=max(mx[ls],mx[rs]);
		pos[i]=mx[i]==mx[ls]?pos[ls]:pos[rs];
	}
	void add(int i,int l,int r,int x,int y,int k){
		if(x<=l&&y>=r)return mx[i]+=k,laz[i]+=k,void();
		down(i);if(x<=mid)add(ls,l,mid,x,y,k);
		if(y>mid)add(rs,mid+1,r,x,y,k);push_up(i);
	}
	pair<int,int> query(int i,int l,int r,int x,int y){
		if(x<=l&&y>=r)return {mx[i],pos[i]};pair<int,int> ans={-1e9,0};
		down(i);if(y<=mid)return query(ls,l,mid,x,y);
		if(x>mid)return query(rs,mid+1,r,x,y);
		auto [val1,P1]=query(ls,l,mid,x,y);
		auto [val2,P2]=query(rs,mid+1,r,x,y);
		return {max(val1,val2),val1>=val2?P1:P2};
	}int operator [](const int &x){return this->query(1,1,n,x,x).first;}
	int operator [](const pair<int,int> x){return this->query(1,1,n,x.first,x.second).first;}
	#undef mid
}T;
int ans=0;
void solver(int l,int r,int Mx){
	// cout<<l<<' '<<r<<'\n';
	if(l>=r)return ;
	auto [mx,pos]=T.query(1,1,n,l,r);
	if(pos!=l)ans=max(ans,T[{l,pos-1}]+mx+Mx);
	if(pos==r)return ;
	if(2*mx<=Mx+T[{pos+1,r}])return ans=max(ans,mx+T[{pos+1,r}]+Mx),void();
	else solver(pos+1,r,Mx);
}
void solvel(int l,int r,int Mx){
	// cout<<l<<' '<<r<<'\n';
	if(l>=r)return ;
	auto [mx,pos]=T.query(1,1,n,l,r);
	if(pos!=r)ans=max(ans,T[{pos+1,r}]+mx+Mx);
	if(pos==l)return ;
	if(2*mx<=Mx+T[{l,pos-1}])return ans=max(ans,mx+T[{l,pos-1}]+Mx),void();
	else solvel(l,pos-1,Mx);
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	// freopen("D.in","r",stdin),freopen("D.out","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	T.build(1,1,n);
	for(int i=1,opt,x,y,k;i<=q;i++){
		cin>>opt>>x>>y;
		if(opt==1){
			ans=-1e9;
			auto [Mx,Pos]=T.query(1,1,n,x,y);
			solvel(x,Pos-1,Mx),solver(Pos+1,y,Mx);
			if(ans==-1e9)cout<<"No\n";
			else cout<<ans<<'\n';
		}else cin>>k,T.add(1,1,n,x,y,k);
	}
}

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

文章操作

相关推荐

评论

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