Reversing an array Query

Question

I have an array of size N and I have given 2 types of query

1 L R Reverse all element from [L,R]
2 L Find the value at 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-Number of Query
Q<=10^5 and N<=10^5
Straight Forward Solution will be O(Q*N) which will be Quite slow, how to make it faster can segment tree can be used ?

Answer 1

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

This can be done in time O((n + q) log n) using decorated splay trees. Each node decoration consists of a descendant count and a bit that, when set, implicitly flips the entire subtree. To query, use the descendant counts to navigate to the proper node. To reverse from u to v, splay u to the root, detach its left subtree u.L, splay v to the root, detach its right subtree v.R, invert the flip bits on all of u.L, v, v.R, reattach u.L to the field from which v.R came, splay u, reattach v.R similarly.

Key: ? denotes an anonymous node
     ^ denotes a subtree


   u
  / \
u.L  ?
 ^  / \
   v   ?
   ^   ^


u.L    v
 ^    / \
     u  v.R
      \  ^
       ?
       ^


v.R    v     # v's flip bit is inverted
 ^    / \
     u  u.L  # so is u.L's, for no effect on u.L
      \  ^
       ?
       ^


   u
  / \
v.R  v
 ^  / \
   ?  u.L
   ^   ^