Please share the approach for XORSEQ. I am unable to understand lowerbound solution
link: CodeChef: Practical coding for everyone
let’s say n = 8
segment (l, r), means this segment has elements from l to r without any cut in it
lower_bound function returns the first occurrence of the element that is greater than or equal to the key element
{(1, 2), (4, 5), (7, 8)}
lower_bound function will return (4,5) for (3, 5) as a key element
return to the main problem
initially, there will be only one segment (1, 8)
for query type 1 x: find a segment that is having x
if x is not the part of any segment then just simply go to the next query
else: find the segment with lower_bound function,
let say the returned segment is (a, b), such that a <= x && x <= b
divide the (a, b) segment to the two non zero sizes different segment if possible
such that (a , x-1) and (x + 1, b)
for query 2:
again use the lower_bound to find the required segment (keeping in the mind about the corner cases)
here is my solution (after contest)
https://www.codechef.com/viewsolution/30751293