Can someone provide the solution to CK87DANC

general
,
1

since the editorials are not out, can someone explain the solution of the problem?

2 Likes
2

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 efficiently

We iterate over i in increasing order. At index i we will answer queries whose R = i. How?
First we find j as described. Observe that for all queries with L \le j and R \ge i, the length of D[j..i] or i-j+1 is a potential answer. We can range update a min segment tree on [1..j] with i-j+1. Then for a query L, R we are sure that that all subarray lengths put into the segment tree have their right endpoints \le R. Now if we query on this segment tree with L we will get the minimum subarray length, which is the answer for the query.

Here is my implementation, if it helps to understand better.

2 Likes
3

Same solution as that of meooow but with suffix implementation. For every i find the minimum j such that Xor of all elements in the range i to j is greater than M. Solution

2 Likes
4

Theres’ also a lot of discussion going on at this link:

5

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 j-i+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 ?

6

try out what you just said , you will have your answer :stuck_out_tongue:

7

@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.