本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-27 07:24:37

写在前面

一道非常不错的题目，侧重思维的 DS 好题，这篇题解是写给自己的题解，应该会比较详细 有错误或疑问可以私信或评论。

题意

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

给定一个长度为 $n$ 的序列 $a$，并给出 $q$ 次询问，询问有两种。

• 给定 $l,r$，你需要选择 $l \le x < y < z \le r$ 的 $x,y,z$，满足 $a_y - a_x \le a_z - a_y$，求最大的 $a_x + a_y + a_z$。
• 给定 $l,r,x$，对 $i \in [l,r]$ 内每个元素 $a_i$ 加 $x$。

$n \leq 10^6,q \le 5 \times 10^4,a_i \le 10^9$。

Solution

首先转化一下题目条件，实际上是要求 $2a_y \le a_x + a_z$，由此我们发现，当 $a_x$ 和 $a_z$ 更大的时候是一定不劣的，我们可以枚举 $y$，维护前后缀最大值，则 $a_x$ 一定是 $[l,x)$ 的最大值，$a_z$ 一定是 $(x,r]$ 的最大值。

有了这个做法，我们不难发现，$a_x$ 与 $a_z$ 中一定有一个是区间最大值，考虑分两种情况分析：

• 当 $a_y$ 取得全局最大值，由于 $2a_y \le a_x + a_z$，所以 $a_x$ 和 $a_z$ 只有和 $a_y$ 相等才会合法。
• 当 $a_y$ 不为全局最大值，此时 $a_x$ 和 $a_z$ 包含了前缀和后缀最大值，也就是包含了整个区间，所以一定有一个是全局最大值。

由此，我们可以先钦定 $a_x$ 作为最大值，统计答案，对于 $a_z$ 的情况同理，只需要反过来做一遍就行了。

考虑 $a_x$ 作为最大值，此时找到 $(x,r]$ 的最大值，记他的位置为 $k$。

• 当 $z = k$ 时，也就是 $z$ 作为 $(x,r]$ 的最大值，此时 $a_x$ 和 $a_z$ 已经是区间 $[x,r]$ 的最大值，因此对于所有 $y \in (x,k)$ 都有 $a_y \le a_x$ 且 $a_y \le a_z$，直接查询区间最大值统计答案即可。
• 当 $y = k$ 时，发现 $z$ 越大一定是不劣的，因此我们需要在 $(k,r]$ 的区间内找到一个最大值，设为 $p$，并尝试统计答案。

对于第二种情况，如果它已经合法，那么对于其它的 $z \in (k,r],z \neq p$，一定不优于 $p$，直接统计答案就结束了。

否则由于它不合法，而 $z = p$ 已经取到 $(k,r]$ 的最大值，$(k,r]$ 内不会有数能够与 $x,k$ 构成合法的三元组，因此只能考虑在 $(k,r]$ 内重新找到一个 $y$，再按照这个方法找到 $z$，直到找到一个合法方案或区间长度不合法。

不难发现我们进入了一个类似的子结构，直接递归查找即可，$a_z$ 作为全局最大值的情况同理，使用线段树维护区间最大值及其位置，维护区间加操作即可。

复杂度分析

这里参考了官方题解的复杂度分析，考虑设 $[l,r]$ 的最大值为 $x_0$，位置为 $p_0$。设区间 $(p_0,r]$ 的最大值为 $x_1$，位置为 $p_1$，依此类推，可以得到 $x_2,x_3 \dots x_m$。

考虑确定 $x$ 为区间最大值，一对 $y,z$ 不合法的条件是 $a_x + a_z < 2a_y$，即 $x_0 + x_2 < 2a_1$，移项得 $x_2 < 2x_1 - x_0$。

考虑递归进下一层，依旧不合法的条件是 $x_0 + x_3 < 2 x_2$，移项得 $x_3 < 2 x_2 - x_0$。

联立得出的两个式子，可得 $x_3 < 2x_2 - x_0 < 2 \times (2x_1 - x_0) - x_0$，也就是

$$x_3 < 2x_2 - x_0 < 4x_1 - 3x_0$$

归纳一下这个式子，也就是

$$x_i < 2^{i - 1}x_1 - (2^{i - 1} - 1)x_0$$

$$x_i < x_0 - 2^{i - 1}(x_0 - x_1)$$

当 $x_0 = x_1$，不妨从 $x_1$ 开始归纳，而当出现 $x_0 = x_1 = x_2$，则直接统计答案就是最优的。由此，递归层数只有 $O(\log V)$ 层，可以直接递归统计答案。

Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int a[maxn];
struct note{
	int lx,rx,mx;
};
note tr[maxn << 2];
int tag[maxn << 2];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)
void pushup(int rt)
{
	if(tr[lson].mx == tr[rson].mx)
	{
		tr[rt] = tr[lson];
		tr[rt].rx = tr[rson].rx;
		return;
	}
	tr[rt].mx = max(tr[lson].mx,tr[rson].mx);
	tr[rt] = (tr[rt].mx == tr[lson].mx ? tr[lson] : tr[rson]);
	return;
}
void build(int rt,int l,int r)
{
	if(l == r)
	{
		tr[rt].mx = a[l];
		tr[rt].lx = tr[rt].rx = l;
		return;
	}
	build(lson,l,mid);
	build(rson,mid + 1,r);
	pushup(rt);
	return;
}
void pushdown(int rt)
{
	if(!tag[rt]) return;
	tr[lson].mx += tag[rt];
	tr[rson].mx += tag[rt];
	tag[lson] += tag[rt];
	tag[rson] += tag[rt];
	tag[rt] = 0;
	return; 
}
void update(int rt,int l,int r,int x,int y,int k)
{
	if(x <= l && r <= y)
	{
		tr[rt].mx += k;
		tag[rt] += k;
		return;
	}
	pushdown(rt);
	if(x <= mid) update(lson,l,mid,x,y,k);
	if(y > mid) update(rson,mid + 1,r,x,y,k);
	pushup(rt);
	return;
}
note query(int rt,int l,int r,int x,int y)
{
	if(x <= l && r <= y) return tr[rt];
	pushdown(rt);
	note res,ls,rs;
	int cnt = 0;
	if(x <= mid) ls = query(lson,l,mid,x,y),cnt++;
	if(y > mid) rs = query(rson,mid + 1,r,x,y),cnt += 2;
	if(cnt == 1) return ls;
	if(cnt == 2) return rs;
	if(ls.mx == rs.mx)
	{
		res = ls;
		res.rx = rs.rx;
	}
	else
	{
		res.mx = max(ls.mx,rs.mx);
		res = (res.mx == ls.mx ? ls : rs);
	}
	return res;
}

int ans;
int n,q;
void ql(int l,int r,int mx)
{
	if(l >= r) return;
	auto it = query(1,1,n,l,r);
	if(it.lx != r) ans = max(ans,mx + it.mx + query(1,1,n,it.lx + 1,r).mx);
	if(it.rx == l) return;
	auto xx = query(1,1,n,l,it.rx - 1);
	if(2 * it.mx <= mx + xx.mx) 
	{
		ans = max(ans,it.mx + mx + xx.mx);
		return;
	}
	ql(l,it.rx - 1,mx);
}

void qr(int l,int r,int mx)
{
	if(l >= r) return;
	auto it = query(1,1,n,l,r);
	if(it.rx != l) ans = max(ans,mx + it.mx + query(1,1,n,l,it.rx - 1).mx);
	if(it.lx == r) return;
	auto xx = query(1,1,n,it.lx + 1,r);
	if(2 * it.mx <= mx + xx.mx) 
	{
		ans = max(ans,it.mx + mx + xx.mx);
		return;
	}
	qr(it.lx + 1,r,mx);
}

signed main()
{
	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,1,n);
	for(int i = 1;i <= q;i++)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int l,r;
			cin >> l >> r;
			ans = -1e9;
			auto it = query(1,1,n,l,r);
			int mx = it.mx;
			ql(l,it.rx - 1,mx);qr(it.lx + 1,r,mx);
			if(ans == -1e9) cout << "No\n";
			else cout << ans << "\n";
		}
		else
		{
			int l,r,x;
			cin >> l >> r >> x;
			update(1,1,n,l,r,x);
		}
	}
	return 0;
}

本人代码常数较大，祝大家 CSP-S2025 rp++。