Exact brute force aolution of this problem.
I am not getting the use os many variables in ur code, which makes the code complicates to find the bug.
So, i would suggest, make a buildBlock(blockno) function, which rebuild block. Whenever there’s an update, just change A[i] and call updateBlock(i/BlockSize). Dont complicate things.
For query, if i belong to first block, calculate answer using brute force, else set prwv = 0, run loop from j = 0 to j< i/blocksize, add map[j].get(prev^k) to count and set prev = prev^xor[j].
Run another loop from j = (i/blocksize)*blocksize to j<= i, prev = prev^A[j], if prev==k, count++. Print count.
Well, you must be tired to hear this again and agin, but practice ia the obly way :). You have to spend quality time with algorithms 
First thing, no need to maintain update array, we can calculate the prev value on the run. Calculating update also increase our work, with ni benefit.
Second thing, U too are complicating your solution, so i would recommend implementing it the way i mentioned in a comment above. Keep things simple, so that debugging is simple.
Friend, i haven’t solved this problem using segtree. I don’t even think there’s are solution using segment trees. The only other solution i know MIGHT be using trie, but i haven’t seen any such solution. Square root decomposition is the most easy one.
If you have any different solution, i would like to see.
No problem…
Friend, though your approach is correct and can work, There are much simpler approaches available.
In the second loop where (i+1) < n && a[i]!=b[i+1]
add one more condition a[i+1] != b[i]
Same for i-1.
Also, You can use the above O(N^2) solution i explained for N <= 4 and Your solution for N>4.
Keep coding.
Yeah, u are right about the part that if N>3, max possible hamming distance = N.
Ur approach, though sounds easier, can be met with a tricky case i guess (cant say surely, as i have not seen ur solution).
I too used a similar idea initially.
My approach
First, create total 3 copies of given array. One original, one sorted in ascending order and one ordered in descending order.
Compare original array with both sorted arrays, and compare hamming distance in both cases. Run above program on array with greater hamming distance.
Friend, i would be able to help u if u explain the idea of ur solution. I havent worked woth fenwick trees…
No, there should not be any break in CHEFHAM solutio.
@taran_1407, I followed your approach while also using the break after swapping the two positions and it got Accepted.
How can taran help you here? 
1 Like
Well @vijju123, i know this would apper suprising to u, but incidently i can :D.
@akshaycs, firstly i would like to congratulate u for getting 100 points without writing actual solution.
After that, the reason your solution worked was weaker test cases for this problem.
Lastly, i would recommend u to solve this question using sqrt decomposition for your practice.
Alright??
When I read the ans, my interpretation was “Brute force got AC, do something about it!” (and hence my confusion :p)
That TC had all small cases. A TLE in it means your code is going either into undefined behavior, or an infinite loop. Look for common errors which cause runtime error to debug easily, array index out of bound etc. are my first bet.
Whenver Ai == Bi, i try to replace it witn any suitable position j, such that Ai != Bj and Aj != Bi, this way, when i swapBi and Bj, Ai != Bi and Aj != Bj, thus reducing hamming distance.
After that, only those positions have Ai ==Bi, for which it is not possible to reduce hamming distance by swap with any other element.
Aftet that, i calculate hamming distance of final array and print answer.
Thanks @taran_1407 for replying. I will try to implement it and let you know if it fails. Apart from that do you have a better approach?
Thanks for the help, as I am just beginning with competitive coding!
Simply u could create a frequency map of elements of array A. Put it in a double ended queue(which stores the element and its frequency).Now traverse the array A,compare A[i] with first element of deque,if (they are not equal then decrease its frequency and print it,if frequency becomes 0 pop it),else if(they are equal do the same procedure for last element of deque)
Well @kushan02, If you wanna have a look at better approach, See my solution for its simplicity, (Everyone tends to like their own solution) or refer many solutions from above comments.
Following is my most favorite solution:
Randomized solution: CodeChef: Practical coding for everyone
Glad to hear that…