since the editorials are not out, can someone explain the solution of the problem? asked 23 Oct '17, 11:41

This is what I gathered from partly seeing a few accepted solutions. For each index $i$ find the largest $j \le i$ such that xor of $D[j..i] \ge M$.A trie can be used for this. This is a good tutorial for the general idea. For this problem a trie node needs to store an additional value along with the left and right child pointers which will be the maximum corresponding index out of all the prefix xor values in the subtree of that node. Answer queries efficientlyWe iterate over $i$ in increasing order. At index $i$ we will answer queries whose $R = i$. How? Here is my implementation, if it helps to understand better. answered 23 Oct '17, 16:31
What is the need of the Segment Tree ? If for query.r=i (i.e. we are at i th position now) and like you said we have also found the largest j such that D[j..i] >= M . Would all the queries whose query.right=i and whose query.left<=j will have ji+1 as their answer while all the queries with queries.right =i and queries.left>j will have 1 as their answer . Can this be a possible solution ?
(23 Oct '17, 19:31)
try out what you just said , you will have your answer :P
(23 Oct '17, 21:15)
@rohan_bose95 no, this will not work because the answer for a query may be a subarray with right endpoint < query.r, but this method only considers D[j..i] which is the smallest subarray with right endpoint = query.r.
(24 Oct '17, 01:08)

Theres' also a lot of discussion going on at this link: http://codeforces.com/blog/entry/55329
link
This answer is marked "community wiki".
answered 24 Oct '17, 09:38
