Problem Link:Contest Author: Mohammad Shahhoud & Said Sryhini Tester: Hasan Jadouh Editorialist: Said Sryheni Difficulty:Medium. Prerequisites :Prefix XOR, Trie Tree, Minimum Range Lazy Segment Tree, Sweep Line. Problem:Given an array of $N$ elements and an integer $M$, you are to answer $Q$ queries. In each query you are given two integers $L$ and $R$. You are to find the minimum range $[i, j]$, that falls completely inside the range $[L, R]$, and the logical $XOR$ of its elements is no less than the given integer $M$. Explanation:Main algorithm:
Extended Explanation:First let's find a more efficent way to calculate the $XOR$ of all the elements inside a given range. We can do so by calculating the prefix $XOR$ for each index in the given array. Let's denote such an array as $Pref$, where $Pref_i = Pref_{i  1} \oplus D_i$. Now the logical $XOR$ for all the elements in the range $[L, R]$ can be calculated as $Pref_R  Pref_{L  1}$. Consider the binary representation of the values of $Pref$ over a 30bit representation. Create a trie tree, where each node has two children ${0, 1}$ denoting the bits of the elements from the given array. The root of the trie tree will contain the most significant bit, while the leaves will contain the least significant bits. Iterate over array's elements from left to right. For each index $i$, we need to find the largest index $j$ such that $Pref_i  Pref_{j  1} \le M$. In order to do so, for each index first insert the value of $Pref_{i  1}$. Now we need to find the largest index inside our trie tree, such that the above mentioned operation holds true. In other words we need to query the formed trie tree passing the value of $Pref_i$. While iterating over the trie, let's define the corresponding bit of $M$ as $B_m$ and the corresponding bit of $Pref_i$ as $B_i$. Also, for each node let's store the value of the maximum index whose binary representation passes through this node, let's denote it as $MX$. In each node we may encounter one of the following two conditions:
Obviously when reaching a leaf node, we need to return the value of $MX$. So far we manages to understand how to efficentely handle step number $1$. Now the problem reduces to: Given ranges $[i, j]$ and queries $[L, R]$, find for each query the smallest range $[i, j]$ that falls completely inside the range $[L, R]$. Moving to step $2$ We build a minimum range lazy segment tree whose leaves are the given queries sorted in nondecreasing order by the value of their $R$. The initial value of each query must be $\infty$.The purpose of such segment tree will be explained below. Sweep over both the left side of each query $[L, R]$ and the left side of the calculated ranges $[i, j]$.
After sweep operation is finished, we can now simply iterate over all the queries by the order given in the input, and query our segment tree for their value. Time Complexity: $O((N + Q) . (log(Q) + log(N)) + N . log(10^9))$ Check setter and tester solutions for the implementation. asked 23 Oct '17, 03:23
