Please share the approach for XORSEQ. I am unable to understand lowerbound solution

link: https://www.codechef.com/GHC32020/problems/XORSEQ/

# Approach for XORSEQ

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