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

· · 题解

写在前面

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

题意

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

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

## 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 ```cpp #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++。