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 MSB of 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 xor 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.
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 MSB of 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 MSB of a_x is i. Obviously, L \leq x \leq R.
- Similarly, let us say present(i) gives us the count of number whose MSB is 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';
}
}
}