Super giant classification discussion is a solution for B. I wrote 6KB for B.

So, the disclaimer is I am very poor at explaining. I can even confuse you more. And thus, I would seriously recommend referring the editorial as the hints, explanation and alternative solution can ease your task. Still if you want to get a gist of my solution, here you go!

So, I hope you know about Hypercube graphs and MIS. Assume graph breaks into 2 parts: A and B with no edges b/w them then, the MIS = MIS(A) + MIS(B). I used DAC for this.

So, consider two nos. u and v which differ by only 1 bit (adjacent nodes in Hypercube graphs). Now, let's have 2 parts: with u in one and v in another. Now, for u and v to be connected, they must differ only at one bit, and all other bits must be same in the suffix.

Consider L XOR R and consider its MSB, with M = 1LL << MSB. Now, we have 2 parts which are the one we talked above. One with numbers with MSB set and one without. Now, the suffix range in the left part is [L Mod M, M — 1] and that in right part is [0, R Mod M].

I will consider 2 cases now: these ranges overlap or not. If they overlap, I can return max(even, odd) for this range. (This is the mistake I was doing early; I was just considering this case). And if they are disconnected, recursively solve them for [L, M — 1] and [M, R]. The answer would be sum of both (as we've discussed above).

And; I assume you would have definitely managed counting of parities in range [0, X] in O(log X) time.

The obvious lower bound is ceil(half), achievable if we take all elements with the same parity of popcount.

Since we're looking for a max. independent set in a bipartite graph (again because parity of popcount), its size is total number of elements — size of maximum matching. Matching $$$2k$$$ with $$$2k+1$$$ gives at most 2 unmatched elements, which are possibly $$$L$$$ and $$$R$$$. That gives us an upper bound that's very close to the previous lower bound. Specifically:

• If $$$L$$$ is even and $$$R$$$ is odd, this case is trivial since we must use exactly one element from each pair $$$(2k, 2k+1)$$$. Which? Those with the same parity of popcount, as mentioned; we can freely choose which parity.
• If $$$L$$$ is odd or $$$R$$$ is even, but not both, there's one unmatched element. We choose the parity of popcount to be equal to this element. The answer is $$$(R-L)/2+1$$$.
• If $$$L$$$ is odd and $$$R$$$ is even, but both have the same parity of popcount, the above still works and the answer is $$$(R-L+1)/2+1$$$.
• If they have different parity of popcount, the upper bound from matching $$$2k$$$ with $$$2k+1$$$ is $$$(R-L+1)/2+1$$$ and the lower bound is $$$(R-L+1)/2$$$, so we just need to find out if there's an augmenting path between $$$L$$$ and $$$R$$$ in that initial matching. If yes, we use the lower bound construction, otherwise we need to figure out a construction that takes $$$L$$$, $$$R$$$ and exactly one element from each pair $$$(2k, 2k+1)$$$.

How to find an augmenting path? Well, if the first bit where $$$(L-1)/2 = l$$$ and $$$R/2 = r$$$ differ is $$$b$$$, then we have paths from l = prefix + 0 + ... to prefix + 0 + 11...1 and from r = prefix + 1 + ... to prefix + 1 + 00...0. These are ranges. Do they overlap and if they do, is it in a way that allows connecting them to make an augmenting path? The answer is: iff $$$r-l \gt 2^b$$$. If that's false, we also get a construction: all elements in the left range with the same parity of popcount as $$$L$$$ and same for the right range.

It requires some effort to figure out due to all the casework but most of that effort is noticing obvious bounds and obvious constructions.