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

· · 题解

考虑一组询问怎么做。称选的数从左到右是 A\ B\ C。

首先 A 或 C 一定是区间最大值。如果你确定了 B，那么 A,C 肯定取两边最大值，所以一定有一个是区间最大值。

现在考虑 A 是最大值，找 A 右边的最大值，设为 u。

然后找 $u$ 右边的最大值 $v$。 - 如果 $A\ u\ v$ 合法，就结束了。 - 否则 $u$ 相关的贡献就算完了，并且以后不需要考虑 $v$ 左边的数（可以调整证明）。继续考虑 $A\ v\ ?$。 然后发现不合法最多 $\log V$ 个。若 $A\ u\ v$ 不合法，则 $A-u < u-v$，也就是 $A-v > 2(A-u)$，也就有值域翻倍的性质。 每次询问需要 $\log V$ 次 RMQ 查询，需要修改，用线段树维护，总复杂度 $\Theta(n+q\log V\log n)$。