[Solution] Binod CodeChef Solution | Solution CodeChef

Problem

A Binod is a person who is very good with bitwise operations. Help Alice solve the following problem and become a Binod.

You are given an array $A$ of $N$ elements. Process $Q$ queries on this array, of the following form:

• Each query contains $5$ integers $k, L_1, R_1, L_2, R_2$. It is guaranteed that $L_1 \leq R_1 \lt L_2 \leq R_2$.
• The answer to a query is the number of pairs $(i, j)$ such that:
  • $L_1 \leq i \leq R_1$ and $L_2 \leq j \leq R_2$
  • $A_i \oplus A_j$ has its $k$-th bit set. Here $\oplus$ denotes the bitwise XOR operation.

Note: An integer $x$ is said to have its $k$-th bit set if the (unique) binary representation of $x$ contains $2^k$. For example, $5 = 101_2 = 2^0 + 2^2$ has its zeroth and second bits set but not the first, while $16 = 10000_2 = 2^4$ has only its fourth bit set.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains two space-separated integers $N$ and $Q$ — the number of elements in array and number of queries, respectively.
  • The second line of each test case contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.
  • The next $Q$ lines describe queries. The $i$-th of these $Q$ lines contains $5$ space-separated integers $k, L_1, R_1, L_2, R_2$ — the parameters described in the statement.

Output Format

For each test case, output $Q$ lines.The $i$-th of these lines should be the answer to the $i$-th query.

Explanation:

Test case $1$: The array is $A = [1, 2, 4, 3, 2]$.

• Query $1$: the ranges are $[1, 3]$ and $[5, 5]$, and $k = 1$. There are three pairs of $(i, j)$: $(1, 5), (2, 5), (3, 5)$.
  • $A_1 \oplus A_5 = 1 \oplus 2 = 3 = 11_2$ has its first bit set
  • $A_2 \oplus A_5 = 2 \oplus 2 = 0 = 0_2$ doesn't have its first bit set
  • $A_3 \oplus A_5 = 4 \oplus 2 = 6 = 110_2$ has its first bit set
  • So, the answer is $2$.
• Query $2$: the ranges are $[1, 2]$ and $[3, 5]$, and now $k = 2$. This time, there are $6$ pairs of indices. Of them, it can be verified that $(1, 3)$ and $(2, 3)$ are the ones that satisfy the given condition.