计算范围数 [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.

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

Count the number of ranges [L; R] which has difference between the maximum and minimum is even

algorithm

stack

deque

segment-tree

rmq