You are given an array \(A\) of length \(N\) and \(Q\) queries. Each query is described by two integers \(L\) and \(R\). For each query, find the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number.
Input Format
- First line contains an integer \(T\), which denotes the number of test cases.
- The first line of each test case contains two integers \(N\) and \(Q\).
- The second line of each test case contains \(N\) space-separated integers, the elements of the array \(A\).
- Next \(Q\) lines contain two space separated integers \(L\) and \(R\).
Output Format
For each test case, print an array of length \(Q\), \(i^{th}\) element will be the answer for the \(i^{th}\) query - the number of tuples \((i, j, k)\) such that \(L \leq i \lt j \lt k \leq R\) and \(A[i] + A[j] + A[k]\) is an odd number.
Constraints
For test case \(1\):
- First Query: \((1, 2, 3)\) is the tuple (1-based indexing) that satisfies the condition as: \(A[1] + A[2] + A[3] = 3 + 3 + 5 = 11\), which is odd. So our answer is \(1\).
- Second Query: \((1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)\) are the tuples (1-based indexing) that satisfy the condition as :
- \(A[1] + A[2] + A[3] = 3 + 3 + 5 = 11\), which is odd.
- \(A[1] + A[2] + A[4] = 3 + 3 + 5 = 11\), which is odd.
- \(A[1] + A[3] + A[4] = 3 + 5 + 5 = 13\), which is odd.
- \(A[2] + A[3] + A[4] = 3 + 5 + 5 = 13\), which is odd.
So our answer is \(4\).
For test case \(2\):
- First Query: There is no tuple that satisfies the condition. So our answer is \(0\).
- Second Query: \((3, 4, 5)\) is the tuple (1-based indexing) that satisfies the condition as: \(A[3] + A[4] + A[5] = 6 + 2 + 5 = 13\), which is odd. So our answer is \(1\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor