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

Question

Given an array n elements (n <= 10^5) Count the number of ranges [L; R] (L <= R) which has difference between the maximum and minimum is even.

For example, n = 5
a[] = {4, 5, 2, 6, 3}
The answer is 11: [1;1], [1;4], [1;5], [2;2], [2;4], [2;5], [3;3], [3;4], [3;5], [4;4], [5;5] The time limit is 1 second

If n <= 1000, a natvie algorithm in O(n^2) will be ok. I think we can improve this approach by using stack or deque. But it's too hard.

Is there any effiecient approach?

Answer 1

One way to get O(n log n) can be to divide and conquer. Divide in the middle and add up the results for left and right. For the section with intervals that overlap the middle, we can use prefixes for max and min and calculate it in O(n). Remember to start the prefixes including both sides of the divide considered together. For the middle section spanning the example, we divide at 2 and have

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

This example isn't great for the next step because there's no change. All together, the middle section of the divide and conquer method for the example, would account for [1;4], [1;5], [2;4], [2;5], [3;4], [3;5].

A more interesting middle:

           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

We see that for each min, we want the counts extending until a lower min on the opposite side, paired with each of the maxes, first with the one it pairs with on the same side plus any lower or equal max on the opposite side, then the rest on the opposite side. We can get the latter in O(1) by storing prefix counts associated with odd maxes. It works because keeping in one direction, the max prefixes are monotonic so we just need the counts of how many of them are odd.

               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)

We perform the iteration in order of decreasing mins (or mirror an iteration on maxes). It doesn't matter which side we start on as long as only one side accounts for one min, and the iteration is sequential.

               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.

Next mins:

               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

Last min:

               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.