统计n≤1e5数组中最值差为偶数的区间数量的高效解法

首先做基础等价转化：两个数的差值为偶数，当且仅当两数奇偶性相同。因此符合要求的区间等价于区间内最大值和最小值奇偶性一致的区间。
我们可以用总区间数减去不符合要求的区间数（最大值、最小值奇偶性不同的区间）得到最终答案，总区间数计算公式为n*(n+1)//2。

高效解法：分治+双指针，时间复杂度O(nlogn) #

该方法实现难度低，且能轻松应对n≤1e5的规模，1秒内可完成计算。

核心思路 #

采用类似求逆序对的分治逻辑：

• 对于当前处理的区间[L, R]，若L == R，直接返回0（单个元素的区间一定符合要求，无不符合项）
• 取中点mid = (L + R) // 2，递归计算左半区间[L, mid]和右半区间[mid+1, R]的不符合区间数，相加得到bad_part
• 计算跨左右两半的不符合区间数bad_cross，当前区间总不符合数为bad_part + bad_cross

跨区间计算优化（O(k)，k为当前区间长度） #

跨区间指左端点在[L, mid]、右端点在[mid+1, R]的区间，我们可以利用单调性用双指针快速统计：

1. 预处理左半区间从mid向左的后缀最大值、后缀最小值：
   当i从mid往L移动时，suffix_max[i] = max(a[i], suffix_max[i+1])，suffix_min[i] = min(a[i], suffix_min[i+1])，可见suffix_max随i左移非递减，suffix_min随i左移非递增
2. 预处理右半区间从mid+1向右的前缀最大值、前缀最小值：
   当j从mid+1往R移动时，prefix_max[j] = max(a[j], prefix_max[j-1])，prefix_min[j] = min(a[j], prefix_min[j-1])，可见prefix_max随j右移非递减，prefix_min随j右移非递增
3. 利用单调性维护四个指针，分别对应四种区间极值来源的边界：
   • 极值都来自左半：prefix_max[j] ≤ suffix_max[i]且prefix_min[j] ≥ suffix_min[i]
   • 最大值来自左半、最小值来自右半：prefix_max[j] ≤ suffix_max[i]且prefix_min[j] < suffix_min[i]
   • 最大值来自右半、最小值来自左半：prefix_max[j] > suffix_max[i]且prefix_min[j] ≥ suffix_min[i]
   • 极值都来自右半：prefix_max[j] > suffix_max[i]且prefix_min[j] < suffix_min[i]
4. 对每种情况分别判断整体最大值、最小值的奇偶性是否不同，统计到bad_cross即可

示例验证 #

题目给出的示例总区间数为5*6//2=15，计算得到不符合要求的区间数为4，因此最终答案为15-4=11，与示例结果一致。

内容的提问来源于stack exchange，提问作者Hiển Nguyễn Minh