题目内容

小红拿到一个长度为 $n$ 的数组 {$a_1,a_2,…,a_n$} 。

她想要知道有多少个三元组 $(i,j,k)$ 满足 $max(a_i-a_j,a_j-a_k)=2×a_j$ 。

请你帮她数一数。

思路

对固定中间位置$j$，记$y=a_j$。令频次函数为$f(x)$，并定义

• $G(t)$：数组中$\ge t$的元素个数，
• $L(t)$：数组中$\le t$的元素个数。

由条件$\max(a_i-a_j,a_j-a_k)=2a_j$可拆分为两种达到最大值的方式，并用容斥合并：

• 当$a_i-a_j=2a_j$时，$a_i=3y$且$a_j-a_k\le 2y \Rightarrow a_k\ge -y$，贡献为$f(3y)\cdot G(-y)$；