MystiXORama

Practice

4 (4 votes)

Bit manipulation

Segment trees

Advanced data structures

Data structures

Problem

58% Success 813 Attempts 50 Points 2.5s Time Limit 256MB Memory 1024 KB Max Code

In a quaint village, there lived a mathematician named Alice. One day, the villagers approached her with a unique challenge. They had an array \(A\) of size \(N\), that held the secrets of their village, and they needed answers to their questions. These questions came in the form of \(Q \) queries. Each query was a request for enlightenment, presented with four mysterious numbers - \(L\), \(R\), \(X\), and \(Y\). For each query, Alice embarked on a journey through the array, focusing on the range from \(L\) to \(R\). She carefully counted how many times each number appeared in this range (from L to R). With this newfound knowledge, she weaved a tapestry of wisdom in the form of a new array, \(B\). For every \(i\) from \(1\) to \(N\): \(B[i]\) = Bitwise XOR of all the numbers that occur exactly \(i\) times in the range \(L\) to \(R\) of array \(A\). If none of the elements in the range from \(L\) to \(R\) occurred \(i\) times, she simply set \(B[i] = 0\). Finally, Alice presented the villagers with the answer to their query, which was nothing short of a revelation. The answer for each query was the sum of the elements in her array \(B\), but only from position \(X\) to \(Y\), for the villagers believed that these specific positions held the key to their query's solution. You now have to help Alice in completing this challenge. Input format The first line contains a single integer \(T\), which denotes the number of test cases. For each test case: The first line contains \(N\) denoting the size of array \(A\). The second line contains \(N\) space-separated integers, denoting the elements of \(A\). The next line contains \(Q\) denoting the number of queries. The next \(Q\) lines contain 4 space-separated integers, denoting \(L\), \(R\), \(X\) and \(Y\). Output format For each test case, print the answer for each query in a new line. Constraints \(1 \leq T \leq 10^3\)\(1 ≤ N ≤ 10^5\)\(1 ≤ A[i] ≤ 10^{9}\ ∀\ i∈[1,N]\)\(1 ≤ Q ≤ 10^5\)\(1 ≤ L ≤ R ≤ N\)\(1 ≤ X ≤ Y ≤ N\)\(\text{The sum of all values of N over all test cases doesn't exceed } 10^5\)\(\text{The sum of all values of Q over all test cases doesn't exceed } 10^5\)

Sample Input

1
7
2 2 1 1 1 5 2
2
2 6 1 2
1 7 1 7

Sample Output

7
8

Explanation

The first line denotes T = 1. For test case \(1\): N = 7 A = [2, 2, 1, 1, 1, 5, 2] Q = 2 Now, For the first query, we are given L=2, R=6, X=1, and Y=2. In range L(=2) to R(=6), elements 2 and 5 occur once, and element 1 occurs three times, so B[1] = 2 ⊕ 5, B[3] = 1, and all the remaining positions of array B will have 0. Array B is [7, 0, 1, 0, 0, 0, 0], and the sum of elements in range X(=1) to Y(=2) of array B is 7. Hence, the answer to the first query is 7. For the Second query, we are given L=1, R=7, X=1, and Y=7. In range L(=1) to R(=7), elements 1 and 2 occur three times, and element 5 occurs once, so B[1] = 5, B[3] = 1 ⊕ 2, and all the remaining positions of array B will have 0. Array B is [5, 0, 3, 0, 0, 0, 0], and the sum of elements in range X(=1) to Y(=7) of array B is 8. Hence, the answer to the second query is 8.

Code Editor

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

Results

Custom Input

Run your code to see the output

Submissions