I solved it using Square Root decomposition technique (Dividing it into sqrt(N) blocks having sqrt(N) elements). I stored the xor for each block in an array. So the update queries took sqrt(N) time (since we need to update only the block in which the updated index lies) and the xor query took sqrt(N) time complexity, since we jump till the block in which the index i lies.
I solved it with sqrt decomposition. Idea is pretty simple. For each block store prefix xor of that block. also keep a variable called totxor storing total xor obtained by all values before that block. So update is clearly root(N) as you just need to update the block. Query is also in root(N). As first u process the start and ending block for that query manually. For rest, suppose for block x you need to find no.of elements having k^block[x].totxor in prefixxor array of that block. Here is my code
I have solved this question using sqrt-decomposition,
First break the array in sqrt(n) blocks then make one hashmap for each block for maintaining counter of each element. For update query update the block and hashmap it will take O(Sqrt(n)) for each query. For type 2 query start from 1st block and for each block increase your result value by counter of A^x(by looking at HashMap).
Here A is initially 0 and its value for a particular block will be the summation of of elements in array having indices less than or equal to last index of previous block.
Only for last block you have to do this work iteratively. This will also take O(Sqrt(n)) for each type 2 query. Therefore time complexity will be O(q * sqrt(n)).
Given an equation A^b=x, you have to find counter of x but you know only values of A(can be calculated) and x. So, we can simply find the counter of b which is A^x. Since A^(A^x)=x.
yes surely. see i am storing count of prefix xor in the block. means suppose my array contents in the block is 2,3,2,4,5. First i do arr[2]++ as its the starting element. Now i do 2^3=1. I do arr[1]++. Then 1^2=3. So i do arr[3]++. Like that
@skyhavoc actually i wasnt sure that the memory limit would pass keeping sqrt(n)=317. You see its already 1e8. Had i kept 317 it would be 3e8. So a precaution. I traded time for space :). 1e8 passes T.L too
I was trying it to do with segment trees …didn’t noticed that even q root(n) complexity would be fine…
Can you explain how to do it with segment trees if possible.
@vishesh_345@asutoshrana I thought about it pretty much too, but I couldn’t come up with a segment tree solution, so I just settled to sqrt decomp too.