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

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

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

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

$A\ ?\ u$ 一定合法，是可以一次 RMQ 算的。

然后找 $u$ 右边的最大值 $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)$。