4

给定一个数组 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 算法就可以了。我认为我们可以通过使用堆栈或双端队列来改进这种方法。但这太难了。

有什么有效的方法吗？

4

1 回答 1

2

一种获得方式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.
于 2021-10-07T16:34:52.737 回答