All Tracks>Data Structures> Advanced Data Structures> Segment Trees> Problem
MystiXORama
★★★★★

4

4 votes
Bit Manipulation, Segment Trees, Advanced Data Structures, Data Structures
Problem

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≤T≤1031≤N≤1051≤A[i]≤109 ∀ i∈[1,N]1≤Q≤1051≤L≤R≤N1≤X≤Y≤NThe sum of all values of N over all test cases doesn't exceed 105The sum of all values of Q over all test cases doesn't exceed 105

 

Sample Input
1
7
2 2 1 1 1 5 2
2
2 6 1 2
1 7 1 7
Sample Output
7
8
Time Limit: 2.5
Memory Limit: 256
Source Limit:
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.
Contributers:
Editor Image

?