计算范围的数量 [L; R]最大值与最小值之差为偶数

Question

给定一个数组 n 个元素 (n <= 10^5) 计算范围的数量 [L; R] (L <= R) 最大值与最小值之差为偶数。

例如，n = 5
a[] = {4, 5, 2, 6, 3}
答案是 11：[1;1], [1;4], [1;5], [2;2], [2;4]、[2;5]、[3;3]、[3;4]、[3;5]、[4;4]、[5;5] 时间限制为 1 秒

如果 n <= 1000，O(n^2) 的 natvie 算法就可以了。我认为我们可以通过使用堆栈或双端队列来改进这种方法。但这太难了。

有什么有效的办法吗？

Answer 1

获得的一种方法O(n log n)是分而治之。中间除以左右的结果相加。对于间隔与中间重叠的部分，我们可以使用 max 和 min 的前缀并在 中计算O(n)。请记住，开头的前缀包括一起考虑的分隔两侧。对于跨越示例的中间部分，我们除以 2 并有

           4, 5, 2, 6, 3
           <------||--->
min pfx    2  2  2||2  2
max pfx    6  6  6||6  6

此示例不适合下一步，因为没有任何更改。总而言之，该示例的分而治之方法的中间部分将占[1;4], [1;5], [2;4], [2;5], [3;4], [3;5]。

更有趣的中间：

           8, 1, 7, 2, 9, 0
           <------||------>
min pfx    1  1  2||2  2  0
max pfx    8  7  7||7  9  9
                 2--7
                 2-----9
              1-----7
              1--------9
           1--------8
           1-----------9
           0--------------9

我们看到，对于每个分钟，我们希望计数延伸到另一侧的较低最小值，与每个最大值配对，首先是与同一侧配对的那个，再加上另一侧的任何较低或相等的最大值，然后剩下的在对面。我们可以通过存储与奇数最大值相关的前缀计数来在 O(1) 中得到后者。它之所以有效，是因为保持在一个方向，最大前缀是单调的，所以我们只需要计算其中有多少是奇数。

               8, 1, 7, 3, 9, 0
               <------||------>
min pfx        1  1  3||3  3  0
max pfx        8  7  7||7  9  9
max odd counts 2  2  1||1  2  3

(Max odd counts do not overlap the middle)

我们按照分钟递减的顺序执行迭代（或镜像最大值迭代）。只要一侧占一分钟，并且迭代是连续的，我们从哪一侧开始并不重要。

               8, 1, 7, 3, 9, 0
               <------||------>
min pfx        1  1  3||3  3  0
max pfx        8  7  7||7  9  9
max odd counts 2  2  1||1  2  3
                     <---
                     <------
[3,7]: extend left to min 1
[3,9]: extend left to min 1
Total: 1 + 1 = 2 overlapping intervals

We could have started on the left and
used the max odd counts on the right:
                     --->-->
[3,7]: extend right to 0, first to
       max 9, then using the max odd
       counts for the remaining window.

接下来的分钟：

               8, 1, 7, 3, 9, 0
               <------||------>
min pfx        1  1  3||3  3  0
max pfx        8  7  7||7  9  9
max odd counts 2  2  1||1  2  3
                  ------>-->
               --------->-->
               
[1,7]: extend right to 0, first
       to max 9, then use the max
       odd count prefixes.
Total: 1 + 1 = 2 overlapping intervals

[1,8]: extend right to 0, first
       to max 9, then use the max
       odd count prefixes.
Total: 1 + 1 = 2 overlapping intervals

最后一分钟：

               8, 1, 7, 3, 9, 0
               <------||------>
min pfx        1  1  3||3  3  0
max pfx        8  7  7||7  9  9
max odd counts 2  2  1||1  2  3
               <---------------
               
[0,9]: extend left to end
Total: 3 overlapping intervals. They don't count, though, since
the difference is not even.