×

# Can someone provide the solution to CK87DANC

 2 since the editorials are not out, can someone explain the solution of the problem? asked 23 Oct '17, 11:41 2.4k●4●20 accept rate: 17%

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.

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.

6★meooow ♦
7.0k717
accept rate: 48%

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 ?

(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) 6★
 2 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 answered 23 Oct '17, 17:27 5★apptica 939●2●10 accept rate: 17%
 0 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 3★skpro19 0 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×484
×187

question asked: 23 Oct '17, 11:41

question was seen: 545 times

last updated: 24 Oct '17, 09:38