Tanya and Rookie Cats (Hard Version)

All submissions for this problem are available.
Tanya still loves cats, even after all the sufferings she's been through because of them. After rigorously training the _batch_, it's now time to fit them into the _squad_. The chosen rookie cats are now to become officers! It's a day of celebration for NCPD, and without any doubt, the most happy person today is Tanya. After all, she is the one who took all the pains to train all of the rookies and transformed them into skilled cats for NCPD, that really is a lot of hard work on her part, so kudos to her for that! Now, there are $N$ officers currently in the _squad_, and Tanya has trained a total of $Q$ rookie cats which have to be accommodated into the _squad_. At NCPD, each cat is assigned an integer ID, which describes the _worthiness_ of a cat, greater is better. The $N$ cats already in the _squad_ have IDs described by the sequence $A$. Although Tanya is the one who has worked the hardest to train these $Q$ cats, but she respects the amount of efforts put by all of her trainees. And out of joy, she has decided to gift _rewards_ to her trainees. There are a total of $Q$ rounds, and in each round a cat with an ID has to be accommodated into $A$. This is how the accommodation process happens for each cat at NCPD:  Tanya gifts a nonnegative integer _reward_ to this cat. The amount of _reward_ is actually the number of cats already in $A$ which have a _worthiness_ strictly lesser than this cat.  This cat gets added into $A$ at the last position. Can you help Tanya figure out the total amount of _rewards_ that she needs to have in order to give it to her loved trainees? ### Input:  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains an integer $N$.  The second line contains $N$ space separated integers $A_{1}, A_{2}, \dots, A_{N}$.  The third line contains an integer $Q$  Each of the next $Q$ lines contain an integer $X$ $(X = W \oplus R)$, where $X$ is the bitwise _XOR_ of the _worthiness_ $W$ of the current cat entering into the _squad_ and the amount of _rewards_ $R$ given so far (excluding the current cat's reward). ### Output: For each test case print a single line containing a single integer, the total amount of reward Tanya needs to give. ### Constraints:  $1 \leq T \leq 10$  $1 \leq N, Q \leq 10^{5}$  $1 \leq A_{i} \leq 10^{9}$, for each valid $i$  $1 \leq W \leq 10^{9}$  All cats (new and old) have unique _worthiness_ ### Subtasks:  **30 points:** $1 \leq N, Q \leq 100$  **70 points:** original constraints ### Sample Input: 1 5 1 2 3 4 5 5 6 2 3 27 16 ### Sample Output: 35 ### Explanation:  **Example Case 1:** Each of the $Q$ accommodations can be seen as follows: $A = [1, 2, 3, 4, 5], \space X = 6 \oplus 0 = 6$ $A = [1, 2, 3, 4, 5, 6], \space X = 7 \oplus 5 = 2$ $A = [1, 2, 3, 4, 5, 6, 7], \space X = 8 \oplus 11 = 3$ $A = [1, 2, 3, 4, 5, 6, 7, 8], \space X = 9 \oplus 18 = 27$ $A = [1, 2, 3, 4, 5, 6, 7, 8, 9], \space X = 10 \oplus 26 = 16$ Finally, $A$ becomes $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]$ and total _rewards_ given are $35$.Author:  ankushkhanna 
Editorial  https://discuss.codechef.com/problems/DWW19G 
Tags  ankushkhanna, ankushkhanna, dwwu2019, fenwicktree, medium, online, policybasedds, segmenttree 
Date Added:  29122019 
Time Limit:  1  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 