[题解] CF1156E Special Segments of Permutation

Special Segments of Permutation

给你一个排列 \(p\)，求有多少个区间 \([l, r]\) 满足 \(p_l + p_r = \max_{i \in [l, r]} p_i\)。
\(n \le 2 \times 10^5\)。

按最大值分治，记当前的分治中心为 \(mid\)，分治区间为 \([l, r]\)。然后需要计算跨分治中心的贡献。

• 如果 \(mid - l < r - mid\)，那么就从 \([l, mid]\) 中枚举一个左端点 \(L\)。
• 如果 \(mid - l > r - mid\)，那么就从 \([mid, r]\) 中枚举一个右端点 \(R\)。

假设现在已经枚举了一个左端点 \(L\)（右端点同理），我们需要做的就是检查 \([mid, r]\) 中是否有一个值为 \(p_{mid} - p_L\) 的数，这个提前预处理出每个值的位置就行。

时间复杂度 \(O(n \log n)\)。