Max Sum OR (Easy Version)

We need maximize $\sum_{i=0}^{r} (a_i | i),$ where $a$ is a permutation of $0,1,\ldots,r$.

The important identity is: $x|y=x+y-(x\&y).$

So $\sum (a_i|i)=\sum a_i+\sum i-\sum(a_i\&i).$

The first two sums are fixed, because $a$ is only a reorder of $0,1,\ldots,r$. Therefore maximizing the OR sum is exactly the same as minimizing $\sum(a_i\&i).$

So the real question is: can we pair numbers so that as many pairs as possible have bitwise AND equal to $0$?

The perfect case

If $r=2^k-1$, then the set is exactly all $k$-bit numbers: $0,1,2,\ldots,2^k-1.$

Then pair every number $x$ with its $k$-bit complement: $a_x=(2^k-1)-x.$

Example for $r=7$: $0\leftrightarrow 7,\quad 1\leftrightarrow 6,\quad 2\leftrightarrow 5,\quad 3\leftrightarrow 4.$

For every pair, $x\&((2^k-1)-x)=0,$ because their bits are exact opposites. That means every OR becomes $2^k-1$, which is obviously as clean as it gets.

What if the prefix is incomplete?

Suppose $r$ is not all ones. Let $m=2^k-1$ be the smallest all-ones mask such that $m\ge r$.

For example, if $r=9$, then $m=15$.

We would love to pair every $x$ with $m-x$, because then $x\&(m-x)=0$. But some complements may be bigger than $r$, which are not allowed. Classic annoying prefix problem.

A number $x$ has valid complement if $m-x\le r.$

That is equivalent to $x\ge m-r.$

So every position $x\in[m-r,r]$ can safely be paired with $m-x.$

These pairs have AND $0$, so they are definitely optimal locally. No downside, no weird trick: if you can make a pair contribute zero to the thing we are minimizing, take it.

Now what remains unpaired?

The positions below $m-r$: $0,1,\ldots,m-r-1.$

And the unused values are exactly the same prefix. So the problem repeats on a smaller $r$: $r'=m-r-1.$

That gives a very simple recursive construction:

1. Find the smallest all-ones mask $m$ with $m\ge r$.
2. For every $x$ from $m-r$ to $r$, set $a_x=m-x.$
3. Recurse on $0,1,\ldots,m-r-1$.

This eventually bottoms out when nothing is left.

Why this is optimal

Look at the highest bit of the current mask $m=2^k-1$. The current range is $[0,r]$ with $2^{k-1}\le r\le 2^k-1$.

The numbers in the upper half have that highest bit set. To make their AND contribution avoid that expensive bit, they should be paired with numbers whose highest bit is not set. Pairing $x$ with $m-x$ does even better: it avoids every shared bit, not just the highest one.

The interval $[m-r,r]$ is exactly the part where this complement is available inside the current prefix. Those elements can be made zero-cost, and zero is the absolute minimum possible contribution. After removing them, the leftover instance is again a smaller prefix, so recursion handles the rest optimally.

Basically: whenever the complement exists, use it. The remaining hole is still the same problem, just smaller. Bitmasks being nice for once. Wild.

Computing the answer

The construction gives the permutation. Then just compute $\sum_{i=0}^{r}(a_i|i)$ with long long.

The easy version has total $n\le 2\cdot 10^5$, so this is easily fast enough. The recursion removes at least one highest-bit block each time, so the total work over a test case is $O(r+1)$.