PROBLEM LINK:
Author & Editoralist: Jafar Badour
Tester: Teja Reddy
PROBLEM EXPLANATION
You are given a sequence of non-negative integers A_1, A_2, \ldots, A_N. A pair (x, y), where 1 \le x \lt y \le N, is an inversion if A_x \gt A_y.
You should answer Q queries (numbered 1 through Q). For each valid i, in the i-th query:
- You are given a non-negative integer K_i.
- Consider a sequence B_1, B_2, \ldots, B_N, where B_j = A_j \oplus K for each valid j.
- You should find the number of inversions in the sequence B.
PREREQUISITES:
None
QUICK EXPLANATION:
Start with bits from most significant to least significant. Find inversions with respect to each bit. After you finish processing the current bit, split elements into 2 vectors (one for numbers having this bit and one for rest). and calculate inversions w.r.t next bit for each vector separately. Answering queries is easy after that.
EXPLANATION:
Letâs assume that we want to solve inversions count on an array of values 0 and 1 only. This can be done easily in linear time. Whenever we encounter a 0 we should add the number of 1s to the left to our inversions count.
Letâs think about the most significant bit b.
Any pair x,y such that (x<y)\,\,AND\,\,(A_x\,\&\,2^b>0)\,\,AND\,\,(A_y\,\,\&\,2^b=0) forms an inversion, regardless of the rest of the binary representation.
Letâs find the number of inversions w.r.t the most significant bit (which is equal to 30 in our problem) and record the number of inversions and denote it with I_{msb}.
What do you think will happen if we flip this bit?
We can find the number of inversions the same way as we did first, whenever we encounter a 1 we should add the number of 0s to the left to our inversions count.
What about the rest of the bits? After finding inversions w.r.t most significant bit, we must find inversions between numbers that have an equal value of this bit.(For different we already did). Split elements into 2 vectors (one for numbers having this bit and one for rest). and calculate inversions w.r.t the next bit (msb-1) for each vector separately.
Letâs denote with I_b the number of pairs (x,y) such that x<y and the first different bit in the binary representation of A_x,A_y is the b_{th} bit, and A_x has this bit turned on.
Letâs say we have a vector v of length l and we are currently processing the bit numbered b and we have found x inversions w.r.t this bit. We flip this bit and calculate the invesions count again (as we did for MSB) and find inversions count after flipping and letâs denote this count by y.
I_b=I_b+x
I'_b=I'_b+y
Try to guess whatâs I'b
How to find an answer for each query?
ans=0
Iterate through all bits from 0 to 30 and letâs say the current has index b
If the bit is turned off:
ans=ans+I_b
Otherwise:
ans=ans+I'_b
#Complexity O(N*log(Max \,A_i))
AUTHORâS AND TESTERâS SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
const int MX = (1<<20);
int arr[MX];
long long inv[100][2];
void solve(int bit , vector < int > v){
if(bit == -1 || v.empty()) return;
int sz = v.size();
int z = 0 , o = 0;
vector < int > v1 , v2;
for(int j = 0 ; j < sz ; j++){
if( (v[j] & (1<<bit)) ){
v1.push_back(v[j]);
++o;
inv[bit][1] += z;
}
else{
v2.push_back(v[j]);
++z;
inv[bit][0] += o;
}
}
solve(bit - 1 , v1);
solve(bit - 1 , v2);
}
int main(){
int T;
scanf("%d",&T);
while(T--){
memset(inv , 0 , sizeof(inv));
int n , QN;
scanf("%d %d",&n,&QN);
vector < int > v;
for(int j = 0 ; j < n ; j++){
int x;
scanf("%d",&x);
v.push_back(x);
}
solve(30 , v);
for(int j = 0 ; j < QN ; j++){
long long ans = 0;
int K;
scanf("%d",&K);
for(int bit = 0 ; bit < 31 ; bit++){
if( (K & (1<<bit)) ) ans += inv[bit][1];
else ans += inv[bit][0];
}
printf("%lld\n",ans);
}
}
}
