I recently tried to solve the following problem. I failed in 30min so I decided to check the editorial. I was quite disappointed that I struggle to follow it and I even more disbelieved that I would ever be able to have the following thought process during future contests. Then after I finally played with the problem and editorial I found another explanation that I think is much easier to follow and better represents actual thought process that one could follow while solving the task. I think most editorials are written by problem setters that often creates problems based on random lemmas that they proof. Then whole editorial is also hard to understand as everything seems to be random. So here is how I think the problem was solved by most contestants. (I'm more than curious to hear from other users if you also agree that editorials are not representing a likely thought process. I also would like to ask problem creators to try to make editorials more realistic :) (Assuming I'm not the only one with the mentioned problem)).
We try to simplify the problem so it's easier to reason about. So let's assume that "l" from query is 0. It's an easier problem as we no longer need to worry about a^x to be less than l as xor won't suddenly make the number negative.
We notice an obvious thing that if "r" is made out of only ones (excluding leading zeros) no matter what smaller x we pick it will work.
If we have Add some additional ones and zeroes on bigger bits of r (and in this way create a new R) all previous x will still work for the new range. (We are still in the simplified version)
Can we even have other working "x"-es? Let's check such a "r" with additional bits 1010[1111].Let's say there is an x that works for range [0, 10101111] but is not a subtask of suffix of ones. Then it means that x has bigger biggest bit than 1000.
Case 1. that biggest bit is not on in our 10101111 that means that after we xor that x with out 10101111 we will get a bigger number so that x cannot exist.
Case 2. That biggest bit is on in our 10101111. Then as our biggest bit of x is not in the suffix of ones there has to be a zero in our 10101111 that is between the biggest bit of x and suffix of once. Let's then consider. number 10101111 but with that 0 bit changes to 1. That new number (let's call it y) has to be bigger than our 10101111. However when we xor that number with our x we will get a number smaller than 10101111 what means that a number not from our range will show up in our range after xor x operation. That means that there had to be a number from our prefix that was mapped to outside of the range. What proofs that the only working x are subsets of suffix of ones.
As we solved the easier task with only [0, r] ranges let's think about [l, r]. If we find x that maps all numbers from [0, r] to [0, r] and [0, l-1] to [0, l-1] it will be a correct x. But we know that all working x are subsets of suffix of ones so to meet both conditions we need to take x that are suffixes for both l-1 and r.
But of course it doesn't prove that those are all x we want to find. Let's assume there is another x that we didn't count already. It still has to map [l, r] to [l, r] but if it doesn't map [0, l-1] to [0, l-1] it has to map it to numbers above r. As we know x cannot have bits on on places outside of r suffix of ones as we already proved it in the 2 cases above that it would map one of bigger numbers to [0, r] but wait now l is bigger than 0 so maybe that number would be mapped to [0, l-1] and [l, r] will still map to itself? That actually could potentially work. Hmm but I don't have any instant ideas let's play with some examples instead.
What if highest big of l is the same as highest bit of r? Then we cannot have that bit on in x as that number will certainly be smaller than l. Hmm so we can reduce the problem by shaving of first bits that are the same. What if the first bits are different? Then if we are looking for x that maps [0, l-1] to numbers bigger than r then we would need to turn biggest bit on. Also then we have to map all of them. Hmm but that means that we need to have enough bigger numbers than r. And number or numbers bigger than r have to equal to numbers in [0, l-1]. But then the number of such mappings is the same as number of mappings that maps [0, l-1] to itself. Has to? I'm not sure but I see that numbers above r with the same biggest bit on are quite similar to numbers in [0, l-1] they are mirrored somehow. So mapping [0, l-1] to [r+1, 1111111] most likely reflects mappings from [0, l-1] to itself. That can work but how to prove that? so we are looking for x that maps [l, r] into [l, r] and [0, l-1] to [r+1, 1111111] hmm then if we have x that works in [0, l-1] mapping then if we xor it with 1111111 we get a correct mapping. Can we get more x-es than those? Hmm no because then it would create a new mapping in [0, l-1] and we counted all. There doesn't seems to be other cases let's submit it :)
