# PROBLEM LINK:

Author: Shahjalal Shohag

Tester: Ildar Gainullin

Editorialist: Rajarshi Basu

# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Prefix Sums

# PROBLEM:

You are given a sequence of integers A_1, A_2, \ldots, A_N. You have to answer Q queries.

In each query, you are given two integers L and R, and you have to find the number of ordered pairs (X, Y) such that L \le X, Y \le R and A_X \le A_X \oplus A_Y \le A_Y. Here, \oplus is the bitwise XOR operator.

#### Constraints

- 1 \le T \le 50,000
- 1 \le N, Q \le 5 \cdot 10^5
- 0 \le A_i \lt 2^{30} for each valid i
- 1 \le L \le R \le N
- the sum of N over all test cases does not exceed 5 \cdot 10^5
- the sum of Q over all test cases does not exceed 5 \cdot 10^5

# EXPLANATION:

## Brief Solution

To satisfy a_x \leq a_x \oplus a_y \leq a_y, the

MSBof a_x must be set in a_y and MSB_{a_y} >MSB_{a_x} .

After this, we can answer the queries in O(log_2 MAX_{A_i}) where MAX_{A_i} = 2^{30} using some prefix sums.

=====================

## How to approach

Ah, a problem about

again. This should immediately make us think about the bitwise notation of a number, instead of some bruting techniques. Let us first assume that we are trying to check for a particular a_x and a_y, a_x < a_y. Try to think about the second condition, ie, a_x \oplus a_y \leq a_y.xor

## Analysing how the bits work

From the upper bound, ie, a_x \oplus a_y \leq a_y, and WLOG assuming a_x < a_y, we can derive the following information:

## Info 1

- notice that MSB_{a_x} \leq MSB_{a_y}, because otherwise a_x > a_y.

## Hint For Info 2

- In bitwise notation, if the k^{th} bit is set, then the number is greater even if all bits till (k-1)^{th} bit is set. Try to apply this along with MSB values of a_x and a_y.

## Info 2

- The MSB_{a_x}^{th} bit must be set in a_y !! Otherwise, a_x \oplus a_y will be greater than a_y. For example consider the following bitwise patterns:

- 101001
- 010010
- The \oplus of the above two numbers is greater than the larger number. However, the following is not:

- 101001
- 001010

## But is that all?

There is however another bound we need to maintain, that is a_x \leq a_x \oplus a_y. How can we ensure that this is maintained? Hint: It’s just a tiny modification to the above informations.

## The tiny change

The only change needed is observing that for the lowerbound to hold, MSB_{a_x} < MSB_{a_y}. Think why on your own. Try to take some examples.

## Final solution idea

To satisfy a_x \leq a_x \oplus a_y \leq a_y, the

MSBof a_x must be set in a_y and MSB_{a_y} >MSB_{a_x} .

## Implementation

## Hint

What can we iterate over in each query?

## Details

- Let us say that for a particular query [L,R], msb(i) means number of values a_x where
MSBof a_x is i. Obviously, L \leq x \leq R.- Similarly, let us say present(i) gives us the count of number whose
MSBis not i but the i^{th} bit is set in that number.- Our answer is S = \sum\limits_{i=0}^{29}{msb(i)*present(i)}. This is true because we are counting unordered pairs

- In order to find msb(i) and present(i) in a particular range [L,R], use prefix sums on each bit. Think about the details on your own

# SOLUTIONS:

## Setter’s Code

```
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
int on[30][N], msb[30][N], z[N];
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t; cin >> t;
assert(1 <= t <= 100000);
int n_sum = 0, q_sum = 0;
while (t--) {
int n, q; cin >> n >> q;
assert(1 <= n && n <= 1000000);
assert(1 <= q && q <= 1000000);
n_sum += n; q_sum += q;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
assert(x >= 0 && x < (1 << 30));
z[i] = z[i - 1] + (x == 0);
int cur_msb = -1;
for (int k = 0; k < 30; k++) {
int b = x >> k & 1;
on[k][i] = on[k][i - 1] + b;
if (b) cur_msb = k;
}
for (int k = 0; k < 30; k++) {
msb[k][i] = msb[k][i - 1] + (cur_msb == k);
}
}
while (q--) {
int l, r; cin >> l >> r;
assert(1 <= l && l <= r && r <= n);
long long ans = 1LL * (z[r] - z[l - 1]) * (r - l + 1);
for (int k = 0; k < 29; k++) {
int a = msb[k][r] - msb[k][l - 1];
int b = on[k][r] - on[k][l - 1];
ans += 1LL * a * (b - a);
}
cout << ans << '\n';
}
}
assert(n_sum <= 1000000);
assert(q_sum <= 1000000);
return 0;
}
```

## Tester’s Code

```
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
using namespace std;
typedef long long ll;
#ifdef iq
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
const int N = 5e5 + 10;
int l[31][N], r[31][N];
int main() {
#ifdef iq
freopen("a.in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
vector <int> a(n);
vector <int> b(n);
vector <int> p(n + 1);
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] == 0) b[i] = 30;
else while (b[i] + 1 < 30 && a[i] >= (1 << (b[i] + 1))) b[i]++;
p[i + 1] = p[i] + (a[i] == 0);
}
for (int z = 0; z <= 30; z++) {
for (int i = 0; i < n; i++) {
int p = (b[i] > z && ((a[i] >> z) & 1));
int q = (b[i] == z);
l[z][i + 1] = l[z][i] + p;
r[z][i + 1] = r[z][i] + q;
}
}
while (q--) {
int vl, vr;
cin >> vl >> vr;
vl--, vr--;
int ret = p[vr + 1] - p[vl];
ll ans = ret * (ll) (vr - vl + 1);
for (int z = 0; z <= 30; z++) {
ans += (l[z][vr + 1] - l[z][vl]) * (ll) (r[z][vr + 1] - r[z][vl]);
}
cout << ans << '\n';
}
}
}
```