Interesting Sections
Contest: Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)
Difficulty rating: 2800
Tags: data structures, divide and conquer, meet-in-the-middle, two pointers

William has an array of non-negative numbers $$$a_1, a_2, \dots, a_n$$$. He wants you to find out how many segments $$$l \le r$$$ pass the check. The check is performed in the following manner:

1. The minimum and maximum numbers are found on the segment of the array starting at $$$l$$$ and ending at $$$r$$$.
2. The check is considered to be passed if the binary representation of the minimum and maximum numbers have the same number of bits equal to 1.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the size of array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{18}$$$), the contents of array $$$a$$$.

Output format:
Output a single number  — the total number of segments that passed the check.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5
1 2 3 4 5

Example output:
9

Example input:
10
0 5 7 3 9 10 1 6 13 7

Example output:
18

Editorial:
We will use Divide & Conquer algorithm.
Let $$$f(l, r)$$$ be the answer to the problem on the subsegment $$$l\ldots r$$$. Let's notice, that if $$$l = r$$$, then $$$f(l, r) = 1$$$, otherwise $$$f(l, r) = f(l, m) + f(m + 1, r) + f'(l, r)$$$, where $$$m = \frac{r + l}{2}$$$ and $$$f'(l, r)$$$ equals to the number of subsegments passing the check, which have left bound ranged from $$$l$$$ to $$$m$$$ (inclusively) and right bound ranged from $$$m+1$$$ to $$$r$$$ (inclusively).
Let's see how to calculate $$$f'(l, r)$$$. Let $$$max(l, r)$$$ be equal to maximum on the subsegment $$$l \ldots r$$$ and $$$min(l, r)$$$ be equal to minimum on the subsegment $$$l \ldots r$$$. Let's suppose that the maximal value of the chosen segment is in the left half (the case when the maximal value is in the right half is similar to this one). Now, let's iterate over the left bound $$$L$$$ of the segment, maintaining a maximal value of numbers in the left half (in other words, a maximal value on the segment $$$L\ldots m$$$). If we iterate over possible $$$L$$$-s in descending order, it is possible to maintain a pointer at all possible right bounds in the right half (notice that we want to maintain the greatest $$$R\_{max}$$$ such that $$$max(m + 1, R\_{max}) \le max(L, m)$$$). Now that we know the maximum, we know the number of bits equal to $$$1$$$ that binary representations of maximum and minimum contain. It's only left to find the number of right bounds $$$R'$$$ such that:
• $$$m + 1 \le R' \le R\_{max}$$$
• $$$min(L, R')$$$ has the same number of bits equal to $$$1$$$ as $$$max(L, m)$$$.
For every prefix of the right half let's calculate the minimum on it, in other words, $$$min(m + 1, pref)$$$, for every $$$pref$$$ such that $$$m + 1 \le pref \le r$$$. Notice that we can maintain an array $$$cnt_x$$$, which for every $$$x$$$ stores the number of right bounds, for which the binary representation of prefix minimum has exactly $$$x$$$ bits equal to $$$1$$$. The only case left unconsidered is when the minimum is in the left half. Let's notice that if we iterate over $$$L$$$-s in descending order, we don't increase the minimum in the left half, which means that we can create a pointer for it in the right half, maintaining such minimal $$$R\_{min}$$$, that $$$min(m + 1, R\_{min}) \le min(L, m)$$$.
It turns out that $$$R\_{min} - (m + 1)$$$ segments have maximum and minimum in the left half, and we know how to find those segments, and we just need to check if the binary representations of maximum and minimum of such segments have equal numbers of bits equal to $$$1$$$. In all other cases we want to calculate the number of right bounds on the segment $$$R\_{min}\ldots R\_{max}$$$, for which the prefix minimum has the same number of bits equal to $$$1$$$ as $$$max(L, m)$$$. It can be done if we maintain the array $$$cnt_x$$$ for the subsegment $$$R\_{min} \ldots R\_{max}$$$.
If we initially calculate the number of bits equal to $$$1$$$ for every number, then we will get a solution in $$$O(n \cdot \log n + n \cdot \log max\_a)$$$.