I recently came across a question that I thought about for a long time without any ideas. I read its solution, but I still didn't understand how to do it.
I've put the problem and part of the solution below in the hope that someone can answer my question.
Given integers $$$n,l,r,x$$$, find an integer sequence $$$a_1 \ldots a_n$$$ such that $$$a_i \in [l,r]$$$, and the XOR sum is $$$x$$$. Maximize $$$\sum_{i=1}^n a_i$$$. If there is a solution, output the largest possible $$$\sum_{i=1}^n a_i$$$. If there is no solution, output -1.
Multiple test cases. $$$1 \leq n \leq 10^9$$$, $$$0 \leq x,l,r \leq 10^9$$$, $$$T \leq 10^6$$$.
And there are some lemmas in the solution,but I can't prove it.
Lemma:
If a solution exists, there are at most $$$\lceil\log_{2}{r}\rceil$$$ numbers $$$a_i$$$ which satisfy $$$a_i < r$$$;
If a solution exists and the highest differing bit position between $$$l$$$ and $$$r$$$ is $$$t$$$, then in the optimal solution there are at most $$$3$$$ numbers $$$a_i$$$ which are less than $$$2^t$$$.
