Accessing Query Array

Question

I have an array of size N and I gave two types of queries

1 LR Flip the entire item from [L, R]
2 L Find the value by the index L.

Example: [1,2,3,4,5] 1 2 4 -> [1,4,3,2,5] 1 4 5 -> [1,4,3,5,2] 2 5 -> 2 

Q - the number of requests
Q <= 10 ^ 5 and N <= 10 ^ 5
The direct solution will be O (Q * N) , which will be rather slow, how to make it faster, can I use a segment tree?

Answer 1

I'm not sure what the segment tree algorithm looks like.

This can be done in O ((n + q) log n) time using decorated trees. Each node decoration consists of counting descendants and bits, which upon installation implicitly flips the entire subtree. To query, use child counting to jump to the corresponding node. To cancel from u to v , splay u to the root, separate its left subtree uL , splay v to the root, disconnect its right subtree vR , invert flip bits on all uL , v , vR , attach uL to the field from which vR came , splay u , reconnect vR .

 Key: ? denotes an anonymous node ^ denotes a subtree u / \ uL ? ^ / \ v ? ^ ^ uL v ^ / \ u vR \ ^ ? ^ vR v # v flip bit is inverted ^ / \ u uL # so is u.L's, for no effect on uL \ ^ ? ^ u / \ vR v ^ / \ ? uL ^ ^