题目分析

我们需要判断是否存在满足条件的三元组 $(i, j, k)$，其中 $1 \le i < j < k \le N$ 且 $H_i - H_j = H_j - H_k$。

解题思路

关键观察

条件 $2H_j = H_i + H_k$ 可以重写为：

这意味着三个数构成等差数列。由于 $H$ 是一个排列，对于每个位置 $j$，我们需要检查是否存在 $i < j < k$ 使得 $H_i$ 和 $H_k$ 关于 $H_j$ 对称。

** 核心思想**

对于每个位置 $j$，考虑以 $H_j$ 为中心的对称性：

• 如果存在 $i < j$ 且 $k > j$ 使得 $H_i + H_k = 2H_j$
• 那么 $H_i$ 和 $H_k$ 关于 $H_j$ 对称

算法设计

使用哈希+线段树的方法来高效检查对称性：

1. 维护两个视图：

   • 左视图 $L$：记录当前位置之前出现的所有数字
   • 右视图 $R$：记录当前位置之后出现的所有数字（通过对称映射）

2. 对称检查：

   • 对于每个 $H_j$，检查左右视图在对称区间内的哈希值是否相等
   • 如果不相等，说明存在不对称，即存在满足条件的三元组

3. 哈希技巧：

   • 使用多项式哈希来表示数字出现的序列
   • 通过线段树维护动态哈希值，支持快速查询和更新

算法详解

数据结构设计

算法流程

1. 预处理：

   g[0] = 1;
   for (LL i = 1; i <= n; ++i)
       g[i] = 1LL * g[i - 1] * base % mod;
   

2. 主循环：

   for (LL i = 1; i <= n; ++i) {
       // 计算对称区间长度
       LL len = min(a[i], n - a[i] + 1);
       
       // 检查左右对称性
       LL left_hash = L.query(1, 1, n, a[i], a[i] + len - 1);
       LL right_hash = R.query(1, 1, n, n - a[i] + 1, n - a[i] + len);
       
       if (left_hash != right_hash) {
           puts("YES");
           return 0;
       }
       
       // 更新线段树
       L.update(1, 1, n, a[i]);                    // 左视图：记录当前数字出现
       R.update(1, 1, n, n - a[i] + 1);           // 右视图：记录对称位置
   }
   

对称性检查原理

对于数字 $x = H_j$，我们检查区间：

• 左视图：$[x, x + len - 1]$
• 右视图：$[n-x+1, n-x+len]$

其中 $len = \min(x, n-x+1)$ 确保不越界。

如果这两个区间的哈希值不同，说明在 $H_j$ 的左右两侧，数字的分布不对称，即存在 $i < j < k$ 使得 $H_i + H_k = 2H_j$。

复杂度分析

• 时间复杂度：$O(N \log N)$
  • 预处理：$O(N)$
  • 主循环：$O(N)$，每次循环进行 $O(\log N)$ 的线段树操作
• 空间复杂度：$O(N)$
  • 线段树：$O(N)$
  • 预处理数组：$O(N)$

正确性证明

该算法的正确性基于以下观察：

1. 充分性：如果存在满足条件的三元组 $(i,j,k)$，那么在处理位置 $j$ 时，左右视图的对称区间哈希值必然不同。

2. 哈希冲突：使用大质数模数和合适的基数，哈希冲突的概率极低，在竞赛数据范围内可以忽略。

3. 完整性：算法检查了每个可能作为中间元素 $H_j$ 的位置，确保不会漏解。

代码总结

本题通过巧妙的哈希技术和线段树维护，将原本需要 $O(N^2)$ 的暴力检查优化到 $O(N \log N)$，体现了算法设计在解决大规模数据问题中的重要性。核心思想是将算术条件转化为对称性检查，利用哈希快速比较序列特征。

对于不同的数据范围，可以选择相应复杂度的算法，但提供的 $O(N\log N)$ 解法能够通过所有测试数据。