# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* rainb0ysimp

*jay_1048576*

**Tester:***iceknight1093*

**Editorialist:**# DIFFICULTY:

2501

# PREREQUISITES:

Observation

# PROBLEM:

A *special permutation* of length N is a sequence of N non-negative integers that contains every integer in [L, L+N-1] exactly once.

You have a permutation of length N.

An integer x is called valid if [A_1\oplus x, A_2\oplus x, \ldots, A_N\oplus x] is a special permutation of length N.

Answer Q queries. In each query, you’re given L and R — find the number of valid integers in the range [L, R].

# EXPLANATION:

N is way too large for anything other than \mathcal{O}(\log N) or \mathcal{O}(1) per query to be viable.

In counting problems like this, often it is useful to be able to nicely characterize the items we’re counting — that is, we should first attempt to figure out what a *valid* x looks like.

Given that the operation at hand is bitwise XOR, it makes sense to look at binary representations.

So, suppose N is a k-bit integer.

Then, it’s not hard to notice that:

- If x is such that
*all*of its last k bits are 0, then x is valid.

This is because for such an x, we have x\oplus i = x + i for i \leq N.

So, the sequence we end up with is [x+1, x+2, \ldots, x+N] which is a special permutation. - If x is such that
*all*of its last k bits are 1, again x is valid.

For such an x, we have x\oplus i = x-i for i \leq N; once again giving us a special permutation.

In fact, these are the only valid types of x.

## Proof

Only the first k bits of x matter here; so let’s discard the higher ones and consider x to be a k-bit integer, i.e, 0 \leq x \lt 2^k.

We’ve already shown that x = 0 and x = 2^k - 1 are valid; with our claim being that no others are valid.

First, if k = 1 then no other x exists since 2^k-1 = 1; so the claim is already true.

Now let’s look at k \geq 2.

Consider two separate cases: either x has the (k-1)-th bit set; or it doesn’t.

That is, either 0 \lt x \lt 2^{k-1}; or 2^{k-1} \leq x \lt 2^k-1.

**Case 1:** 0 \lt x \lt 2^{k-1}

In particular, notice that this means x \lt N.

So, we’ll definitely have x\oplus x = 0 in our xor-ed sequence.

This means the only way it could form a special permutation is if we had everything in range [0, N-1].

However, we can see that we’re missing x itself from that range, since it can only be formed by 0\oplus x = x which we don’t have.

Such an x is thus invalid.

**Case 2:** 2^{k-1} \leq x \lt 2^{k}-1

Once again, the proof is similar.

It can be seen that our xor-ed sequence will contain 2^k - 1; and so once again the only way for it to form a special permutation is if we had the N consecutive integers ending at 2^k - 1.

However, x itself is one of these integers; and again we don’t have 0\oplus x = x in the xor-ed sequence.

Once again, such an x is invalid.

This completes the proof.

Now, given L and R, we need to count for each of the two types above, how many of them lie in range [L, R].

That’s not too hard with the following observations:

- The last k bits of x are 0 if and only if x is a multiple of 2^k.

The number of multiples of 2^k in [L, R] can be found using the formula \left\lfloor \frac{R}{2^k} \right\rfloor - \left\lfloor \frac{L-1}{2^k} \right\rfloor

This follows from the fact that for any a, b, there are \lfloor \frac{a}{b} \rfloor multiples of b that are \leq a. - The last k bits of x are 1 if and only if x+1 is a multiple of 2^k.

To count such numbers, we can instead just count multiples of 2^k in the range [L+1, R+1] using the above formula.

So, knowing k, each query can be answered in \mathcal{O}(1) time.

Finding k is easy in \mathcal{O}(\log N): just find the smallest integer k such that 2^k \gt N.

# TIME COMPLEXITY

\mathcal{O}(\log N + Q) per testcase.

# CODE:

## Author's code (C++)

```
#include "bits/stdc++.h"
using namespace std;
#define int long long
void anubhav(){
int n, q;
cin >> n >> q;
int cnt = log2l(n) + 1;
int x = (1LL << cnt);
while(q--){
int l, r;
cin >> l >> r;
int rr = r / x;
int ll = l / x - (l % x == 0);
int ans = 2 * (rr - ll);
int u = ((l + x - 1) / x) * x;
int v = ((r + x - 1) / x) * x;
if(u - 1 < l || (u) == n) ans--;
if(v - 1 <= r && v - 1 >= l && v > r) ans++;
cout << max(0LL, ans) << "\n";
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1;
cin >> T;
while(T--) anubhav();
return 0;
}
```

## Tester's code (C++)

```
/*...................................................................*
*............___..................___.....____...______......___....*
*.../|....../...\........./|...../...\...|.............|..../...\...*
*../.|...../.....\......./.|....|.....|..|.............|.../........*
*....|....|.......|...../..|....|.....|..|............/...|.........*
*....|....|.......|..../...|.....\___/...|___......../....|..___....*
*....|....|.......|.../....|...../...\.......\....../.....|./...\...*
*....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
*....|.....\...../.........|....|.....|.......|.../........\...../..*
*..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
*...................................................................*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
#define MOD 1000000007
int count(int n,int p,int x)
{
if(x<n)
return 0;
int ans = 2*(x/p);
if((x+1)%p==0)
ans++;
return ans;
}
void solve(int tc)
{
int n,q;
cin >> n >> q;
int p=1;
while(p<=n)
p*=2;
while(q--)
{
int l,r;
cin >> l >> r;
cout << count(n,p,r)-count(n,p,l-1) << '\n';
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tc=1;
cin >> tc;
for(int ttc=1;ttc<=tc;ttc++)
solve(ttc);
return 0;
}
```

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, q = map(int, input().split())
p = 2 ** len(bin(n)[2:])
while q > 0:
L, R = map(int, input().split())
q -= 1
ans = 0
# Multiples of p in [L, R]
ans += R//p - (L-1)//p
# k*p - 1 in [L, R] -> multiples of p in [L+1, R+1]
ans += (R+1)//p - L//p
print(ans)
```