INVZCNT Unofficial editorial

The basic idea was to harness the property of XOR, as we couldn’t evaluate inversions again and again.

When xth bit in xor query is 1, that bit gets flipped for all elements in array. Now for a subsequence of array where the bits greater than x are same, then all elements which had xth bit as 0 and 1 get relatively swapped. Now we consider all pair of numbers where first element has 0 as its xth bit and second has 1 as its xth bit with all greater bits same. For all such pair, we can store inversion count, and count of pairs not inverted (non-inversion count). This non-inversion count becomes inversion count if xth bit is 1 in xor query.

Now the sum of all such inversion counts will give total inversion count.

Eg: For array: 3 4 2 1 7 6 5
All elements are same till 4th bit.

3rd bit
We divide into subproblems as per value of 3rd bit
There are two sides 3 2 1 and 4 7 6 5. Inversion count(inv) among them is 2 (4,2 and 4,1). Increase count(inc) is 10 (3,4 3,7 3,6 3,5 2,7 2,6 2,5 …)
Inv[3]=2 Inc[3]=10

2nd bit
We have two subproblems. 3 2 1 and 4 7 6 5, and we further divide each of them as per value in 2nd bit

For 3 2 1, we split it as 3 2 and 1.
inv=2 inc=0
For 4 7 6 5 we split as 4 5 and 6 7.
inv=2 inc=2
Thus for 2nd bit,
Inv[2]=4 Inc[2]=2

1st bit
We further get 4 subproblems and we further divide them as per value in 1st bit.

1   :inv=0 inc = 0
3 2 :inv=1 inc = 0
4 5 :inv=0 inc = 1
7 6 :inv=1 inc = 0

Inv[1]=2 Inc[1]=1

When we get an xor query, if ith bit is 1 we add Inc[i] it else add Inv[i]

Output:
0: 2+4+2 = 8
1: 2+4+1 = 7
5: 10+4+1 = 15

9 Likes

Thanks a lot. This made things a lot clearer.:grinning:

1 Like