Link

题解

降智了。。。

首先我们不需要关心 \(Len\) 是多少，只需要找到长度为 \(3\) 的等差子序列就行了。

然后就枚举中点 \(mid\)，看看存不存在 \(l<mid<r\) 使得 \(a_{mid}-a_l=a_r-a_{mid}\) 就行了。

这等价于是否存在 \(a_{mid}+k\) 和 \(a_{mid}-k\) 分别在 \(a_{mid}\) 的两边。

把它转化一下变成 check \(a_{mid}+k\) 和 \(a_{mid}-k\) 是否都在 \(a_{mid}\) 的一侧。

这个好做，我们只考虑 \(a_{mid}\) 左边的元素，设 \(vis_i\) 为 \(i\) 是否在 \(a_{mid}\) 左侧，那么需要满足 \(vis_{a_{mid}-k}=vis_{a_{mid}+k}\ (1\le a_{mid}-k\le a_{mid}+k\le n)\)

这个好办，把 \(01\) 序列转成哈希的形式，直接树状数组维护正反区间的哈希值即可，check 就直接提取出正反两个区间的哈希值判断。

时间复杂度：\(O(Tn\log n)\)

AC Code

https://www.luogu.com.cn/record/98864704