题解

思路

把不含所求三元组的区间称为坏区间。

做法

序列值只有 $1$ 到 $10$：若区间长度至少为 $21$，根据鸽巢原理某个值至少出现三次，这三个相等的值已经组成等差子序列。因此坏区间长度至多为 $20$，只需从每个左端点向右检查最多 $20$ 个元素。

扩展窗口时维护 seen[v] 表示值 $v$ 已出现，以及 need[v] 表示此前存在一对下标 $i<j$ 使 $2A_j-A_i=v$。加入新值 $x$ 时，若 need[x] 为真，窗口已经包含等差三元组，后续所有扩展也都是好区间；否则用每个已出现的 $y$ 产生期待值 $2x-y$，再标记 $x$ 已出现。累计所有仍未变好的短窗口得到坏区间数，用总区间数减去它。

复杂度

时间复杂度为 $O(10\times20\times N)$，空间复杂度为 $O(10)$。