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

· · 题解

注意到若枚举 y，则 x 取前缀最大值，z 取后缀最大值。

一旦这样的 y 非法，说明 2y>x+z,x<2y-z。

由对称性，假设 y 处于最大值前面，若连续出现非法情况，有：

a_1<2a_2-A<2(a_3-A)-a_2<2(2(a_4-A)-A)-A<\cdots

不难发现连续非法只有 O(\log V) 次，因此一定包含前 O(\log V) 大值。

用线段树维护，注意不要预处理每个点的前 k 大，而是用的时候计算，否则常数较大。

时间复杂度 O(n+q\log^2 n)。