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)\)。
- 题解 Permutation Segments Special 1156E题解permutation segments special educational permutation codeforces special 题解segments 193d two 题解permutation 167d good 题解permutation another problem 题解 前缀permutation abnormal 题解permutation p7972 2021 题解permutation abnormal version 题解permutation 213e two 线段 题解permutation separation