Max Sum OR (Hard Version)

We need permute the interval $[l,r]$ against itself to maximize

$\sum_{x=l}^{r} (x|mate_x).$

The first trick is the standard OR-to-AND flip:

$x|y=x+y-(x\&y).$

Across all pairs, every number in $[l,r]$ appears once as a fixed $b_i$ value and once as a permuted $a_i$ value, so

$\sum (x+y)=2\sum_{v=l}^{r}v$

is fixed. Therefore maximizing OR is exactly minimizing

$\sum (x\&mate_x).$

So the real problem is: pair numbers so they share as few 1 bits as possible.

Bit-by-bit view

For one bit $j$, a pair contributes $2^j$ to the AND only if both numbers have bit $j$ equal to $1$.

If the current interval has some numbers with bit $j=0$ and some with bit $j=1$, then pairing a zero-bit number with a one-bit number is good: this bit contributes to the OR, but not to the AND.

So at each important bit, we want as many cross-pairs as possible.

The recursive structure

Define solve(l, r, j) to pair every number in the current interval $[l,r]$, considering bits from $j$ down to $0$.

The recursion maintains this idea: all bits above $j$ are already identical inside the current interval, or already forced. So bit $j$ has a simple shape inside a contiguous interval: all the 0s come first, then all the 1s.

There are two cases.

Case 1: bit $j$ does not split the interval

If every number in $[l,r]$ has the same bit $j$, this bit does not create any choice.

If all have bit $0$, no pair pays this bit in the AND.

If all have bit $1$, every pair pays this bit in the AND.

Either way, the pairing decision depends only on lower bits, so we call

$solve(l,r,j-1).$

Case 2: bit $j$ splits the interval

Let the split be

$[l,mid] \quad\text{and}\quad [mid+1,r],$

where the left block has bit $j=0$ and the right block has bit $j=1$.

Let

$t=mid+1.$

Now pair outward from the boundary:

$t-1 \leftrightarrow t,$ $t-2 \leftrightarrow t+1,$ $t-3 \leftrightarrow t+2,$

and so on while both numbers are inside $[l,r]$.

For every such pair, if

$x=t-1-d,\quad y=t+d,$

then

$x+y=2t-1.$

Because $t$ is exactly where bit $j$ turns from $0$ to $1$, the lower $j$ bits of $x$ and $y$ are complements. Also their bit $j$ values are opposite. So these pairs have zero AND contribution on bits $0,1,\dots,j$.

That is as good as it gets. You cannot do better than zero.

Why this is optimal

At bit $j$, suppose the two blocks have sizes $A$ and $B$.

You can make at most $\min(A,B)$ cross-pairs. Any extra numbers on the larger side must pair among themselves. If the larger side is the 1 side, those extra pairs are forced to pay bit $j$ in the AND. If the larger side is the 0 side, they pay nothing for bit $j$.

So pairing as many cross-pairs as possible is mandatory for optimality.

Among those cross-pairs, the symmetric pairing is also optimal because it makes the lower bits complementary, giving zero lower-bit AND for those pairs. No hidden tax, no annoying catch.

After removing all possible cross-pairs, at most one side has leftovers. Those leftovers cannot be paired across bit $j$ anymore, so their bit-$j$ situation is forced. The only remaining choices are in lower bits, which is exactly the smaller recursive problem.

That proves the divide-and-conquer construction is optimal.

Computing the answer

The recursion directly fills mate[x], the number paired with $x$. Then we compute

$\sum_{x=l}^{r}(x|mate[x])$

by a simple loop.

The recursion has only $30$ bit levels, and each level scans/pairs pieces of the interval. With

$\sum n\le 2\cdot 10^5,$

this is easily fast enough. No need to summon a segment tree for a fistfight.